Day 9 第四章 字符串part02

• 今日任務
  • 28.實現 strStr(); 459.重復的子字符串; 字符串總結; 雙指針回顧

28. 實現 strStr() （本題可以跳過）

• 因為KMP算法很難，大家別奢求 一次就把kmp全理解了，大家剛學KMP一定會有各種各樣的疑問，先留著，別期望立刻啃明白，第一遍了解大概思路，二刷的時候，再看KMP會
  好懂很多。
• 或者說大家可以放棄一刷可以不看KMP，今天來回顧一下之前的算法題目就可以。
• 因為大家 算法能力還沒到，細扣 很難的算法，會把自己繞進去，就算別人給解釋，只會激發出更多的問題和疑惑。所以大家先了解大體過程，知道這么回事， 等自己有
  算法基礎和思維了，在看多看幾遍視頻，慢慢就理解了。
• 題目鏈接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
• 視頻講解：1. 幫你把KMP算法學個通透！（理論篇）； 2. 幫你把KMP算法學個通透！（求next數組代碼篇）_嗶哩嗶哩_bilibili
• 文章講解：https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html
• 參考視頻：https://b23.tv/2Px1QbL

KMP 思路

KMP 代碼

public static int strStr(String haystack, String needle) {char origin[] = haystack.toCharArray(); //原始數組char pattern[] = needle.toCharArray();  //模式數組int next[] = next(pattern); //最長前后綴數組//System.out.println(Arrays.toString(next));/*1. 匹配成功，i++ j++，直到j==模式字符串長度2. 匹配失敗j != 0 跳過最長前后綴字符，繼續匹配j == 0 則 i++*/int i = 0;int j = 0;//沒匹配到就一直匹配，直到模式字符串尾部和原始字符串對齊while(pattern.length - j <= origin.length - i){if(origin[i] == pattern[j]){    //匹配成功的情況i ++;j ++;} else if (j == 0) {i++;} else{j = next[j - 1];}//找到解if(j == pattern.length) return i - j;}return -1;
}/*最長前后綴數組：只跟模式字符串有關1. 索引：使用了模式字符串前j個字符串-12。 值：最長前后綴的長度（恰好是匹配失敗時j要跳轉的位置）*/
public static int[] next(char[] pattern){//return new int[]{0,0,1,2,3,0,1};int next[] = new int[pattern.length];int i = 1;int j = 0;/*遇到相同的字符：記錄共同前后綴長度，長度即為 j + 1長度記錄至數組i索引處然后i++ j++遇到不同字符：1. 前面沒有共同部分：j=02. 前面有共同部分，j向回找無需對比的地方，可以跳過無需對比的字符串個數之前已經計算過*/while(i < pattern.length){if(pattern[i] == pattern[j]){next[i] = j + 1;i ++;j ++;}else if(j == 0){i ++;}else{j = next[j - 1];}}return next;
}

459.重復的子字符串 （本題可以跳過）

• 本題算是KMP算法的一個應用，不過 對KMP了解不夠熟練的話，理解本題就難很多。
• 我的建議是 KMP和本題，一刷的時候 ，可以適當放過，了解怎么回事就行，二刷的時候再來硬啃
• 題目鏈接：https://leetcode.cn/problems/repeated-substring-pattern/
• 視頻講解：https://www.bilibili.com/video/BV1cg41127fw/
• 文章講解：https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html

暫時跳過

字符串總結

• 比較簡單，大家讀一遍就行
• 文章講解：https://programmercarl.com/%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%80%BB%E7%BB%93.html

雙指針回顧

• 此時我們已經做過10到雙指針的題目了，來一起回顧一下，大家自己也總結一下雙指針的心得
• 文章講解：https://programmercarl.com/%E5%8F%8C%E6%8C%87%E9%92%88%E6%80%BB%E7%BB%93.html