目錄：

解題及思路學(xué)習(xí)

28.?實現(xiàn)?strStr()

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

給你兩個字符串?haystack?和?needle?，請你在?haystack?字符串中找出?needle?字符串的第一個匹配項的下標(biāo)（下標(biāo)從 0 開始）。如果?needle?不是?haystack?的一部分，則返回??-1?****。

示例 1：

輸入：haystack = "sadbutsad", needle = "sad"
輸出：0
解釋："sad" 在下標(biāo) 0 和 6 處匹配。
第一個匹配項的下標(biāo)是 0 ，所以返回 0 。

思考：字符串匹配，可以直接暴力方法。但是這題肯定是kmp算法。

前綴表：前綴表是用來回退的，它記錄了模式串與主串(文本串)不匹配的時候，模式串應(yīng)該從哪里開始重新匹配。

使用前綴表，就不會從頭匹配，而是從上次已經(jīng)匹配的內(nèi)容開始匹配，找到了模式串中第三個字符b繼續(xù)開始匹配。

**前綴表是如何記錄的呢？**什么是前綴表：記錄下標(biāo)i之前（包括i）的字符串中，有多大長度的相同前綴后綴。

前綴是指不包含最后一個字符的所有以第一個字符開頭的連續(xù)子串。

后綴是指不包含第一個字符的所有以最后一個字符結(jié)尾的連續(xù)子串。

前綴表要求的就是相同前后綴的長度。

所以字符串a(chǎn)的最長相等前后綴為0。 字符串a(chǎn)a的最長相等前后綴為1。 字符串a(chǎn)aa的最長相等前后綴為2。 等等…。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-pXWB2jJR-1691982232460)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/0577fe82-fba0-498e-8995-e7eca0fbc040/Untitled.png)]

前綴表可以告訴我們匹配失敗之后跳到哪里重新開始匹配。

下標(biāo)5之前這部分的字符串（也就是字符串a(chǎn)abaa）的最長相等的前綴 和 后綴字符串是 子字符串a(chǎn)a ，因為找到了最長相等的前綴和后綴，匹配失敗的位置是后綴子串的后面，那么我們找到與其相同的前綴的后面重新匹配就可以了。

如何計算前綴表

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-mC760OQe-1691982232464)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/87bd2181-9cb1-4836-ad3f-6a2dd4a50f59/Untitled.png)]

可以看出模式串與前綴表對應(yīng)位置的數(shù)字表示的就是：下標(biāo)i之前（包括i）的字符串中，有多大長度的相同前綴后綴。

KMP算法的時間復(fù)雜度是O(n+m)的。暴力的解法顯而易見是O(n × m)，所以KMP在字符串匹配中極大地提高了搜索的效率。

構(gòu)造next數(shù)組

構(gòu)造next數(shù)組其實就是計算模式串s，前綴表的過程。?主要有如下三步：

1. 初始化
2. 處理前后綴不相同的情況
3. 處理前后綴相同的情況

前綴表統(tǒng)一減一的操作

class Solution {
public:void getNext(int* next, const string& s) {int j = -1;next[0] = j;for(int i = 1; i < s.size(); i++) { // 注意i從1開始while (j >= 0 && s[i] != s[j + 1]) { // 前后綴不相同了j = next[j]; // 向前回退}if (s[i] == s[j + 1]) { // 找到相同的前后綴j++;}next[i] = j; // 將j（前綴的長度）賦給next[i]}}int strStr(string haystack, string needle) {if (needle.size() == 0) {return 0;}int next[needle.size()];getNext(next, needle);int j = -1; // // 因為next數(shù)組里記錄的起始位置為-1for (int i = 0; i < haystack.size(); i++) { // 注意i就從0開始while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配j = next[j]; // j 尋找之前匹配的位置}if (haystack[i] == needle[j + 1]) { // 匹配，j和i同時向后移動j++; // i的增加在for循環(huán)里}if (j == (needle.size() - 1) ) { // 文本串s里出現(xiàn)了模式串treturn (i - needle.size() + 1);}}return -1;}
};

• 時間復(fù)雜度: O(n + m)
• 空間復(fù)雜度: O(m), 只需要保存字符串needle的前綴表

前綴表（不減一）C++實現(xiàn)

i表示后綴末尾，ji傲視前綴末尾。

class Solution {
public:void getNext(int* next, const string& s) {int j = 0;next[0] = 0;for(int i = 1; i < s.size(); i++) {while (j > 0 && s[i] != s[j]) {j = next[j - 1];}if (s[i] == s[j]) {j++;}next[i] = j;}}int strStr(string haystack, string needle) {if (needle.size() == 0) {return 0;}int next[needle.size()];getNext(next, needle);int j = 0;//使用next數(shù)據(jù)，將haystack與needle進行匹配。for (int i = 0; i < haystack.size(); i++) {while(j > 0 && haystack[i] != needle[j]) {j = next[j - 1];}if (haystack[i] == needle[j]) {j++;}if (j == needle.size() ) {  // 文本串s里出現(xiàn)了模式串treturn (i - needle.size() + 1);}}return -1;}
};

• 時間復(fù)雜度: O(n + m)
• 空間復(fù)雜度: O(m)

多自己寫幾遍，就會理解的更深一點。

459.重復(fù)的子字符串

https://leetcode.cn/problems/repeated-substring-pattern/

給定一個非空的字符串?s?，檢查是否可以通過由它的一個子串重復(fù)多次構(gòu)成。

示例 1:

輸入: s = "abab"
輸出: true
解釋: 可由子串 "ab" 重復(fù)兩次構(gòu)成。

思考：最多由一半的子串組成。利用kmp算法不斷找最小重復(fù)子串。

隨想錄：判斷字符串s是否由重復(fù)子串組成，只要兩個s拼接在一起，里面還出現(xiàn)一個s的話，就說明是由重復(fù)子串組成。當(dāng)然，我們在判斷 s + s 拼接的字符串里是否出現(xiàn)一個s的的時候，要刨除 s + s 的首字符和尾字符，這樣避免在s+s中搜索出原來的s，我們要搜索的是中間拼接出來的s。

class Solution {
public:bool repeatedSubstringPattern(string s) {string t = s + s;t.erase(t.begin());t.erase(t.end() - 1);if (t.find(s) != std::string::npos) return true;return false;}          
};

• 時間復(fù)雜度: O(n)
• 空間復(fù)雜度: O(1)

kmp思路：

最長相等前后綴不包含的子串就是最小重復(fù)子串

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-7OWiy2H8-1691982232465)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/df6b2f6b-6ed3-441d-9fee-ffe8dbba32ff/Untitled.png)]

數(shù)組長度減去最長相同前后綴的長度相當(dāng)于是第一個周期的長度，也就是一個周期的長度，如果這個周期可以被整除，就說明整個數(shù)組就是這個周期的循環(huán)。

class Solution {
public:void getNext (int* next, const string& s){next[0] = 0;int j = 0;for(int i = 1;i < s.size(); i++){while(j > 0 && s[i] != s[j]) {j = next[j - 1];}if(s[i] == s[j]) {j++;}next[i] = j;}}bool repeatedSubstringPattern (string s) {if (s.size() == 0) {return false;}int next[s.size()];getNext(next, s);int len = s.size();if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {return true;}return false;}
};

• 時間復(fù)雜度: O(n)
• 空間復(fù)雜度: O(n)

字符串總結(jié)

1、C語言中，已結(jié)束符’\0’ 判斷字符串是否結(jié)束。C++中，提供一個string類，string類會提供 size接口，可以用來判斷string類字符串是否結(jié)束，就不用’\0’來判斷是否結(jié)束。

2、那么vector< char > 和 string 又有什么區(qū)別呢？其實在基本操作上沒有區(qū)別，但是 string提供更多的字符串處理的相關(guān)接口，例如string 重載了+，而vector卻沒有。所以想處理字符串，我們還是會定義一個string類型。

3、打基礎(chǔ)的時候，不要太迷戀于庫函數(shù)。

4、雙指針法在數(shù)組，鏈表和字符串中很常用。其實很多數(shù)組填充類的問題，都可以先預(yù)先給數(shù)組擴容帶填充后的大小，然后在從后向前進行操作。

5、KMP的主要思想是當(dāng)出現(xiàn)字符串不匹配時，可以知道一部分之前已經(jīng)匹配的文本內(nèi)容，可以利用這些信息避免從頭再去做匹配了。

復(fù)盤總結(jié)

個人反思

字符串類類型的題目，往往想法比較簡單，但是實現(xiàn)起來并不容易，復(fù)雜的字符串題目非常考驗對代碼的掌控能力。

雙指針法是字符串處理的常客。

KMP算法是字符串查找最重要的算法