目錄

注意:?

next數組的變化規律：

初始化：

求next數組部分：

KMP部分：

AC代碼：

---

題目鏈接：【模板】KMP - 洛谷

注意:?

1、next數組是針對子串的，并未涉及母串，因此求next數組時與母串無關
2、在KMP算法中，字符串的起始下標為1，這樣子方便操作，因此我們讀入s母串和p子串后，要s = '0' + s; p = '0' + p

求解字符串的next數組，要提前知道next數組的變化規律

next數組的變化規律：

1、若j的位置和i的位置匹配上了，則next[j + 1] = next[j] + 1，注意如果匹配上了，next數組一定是 + 1遞增的，跨度只能是1
2、若j的位置和i的位置沒匹配上，則j = next[j]，回退到next[j]的位置

初始化：

求next數組部分：

1、該部分只涉及子串
2、next[1] = 0;
3、for遍歷i，只走一次，不回退，且i初始化為2，因為next[1]已經被定義了
4、j從0開始

KMP部分：

1、for遍歷i，只走一次，不回退，i初始化為1（注意這里和next數組的不同），且for用來遍歷母串
2、j從0開始，遍歷的是子串??

AC代碼：

const int N = 1e6 + 5;int nextt[N];void GetNext(const string& p)
{nextt[1] = 0;int n = p.size() - 1;//因為在字符串前面加了個'0'，所以字符串的長度 = 字符串的size - 1for (int i = 2, j = 0/**/; i <= n; i++){while (j && p[j + 1] != p[i])/*注意有一個 + 1，要判斷的是下一個位置是否和i位置相等*/j = nextt[j];//回退if (p[j + 1] == p[i])//如果匹配上了j++;//繼續往后走，不回退nextt[i] = j;//注意是next[i]，并不是next[j]}
}void KMP(const string& s, const string& p)
{int len1 = s.size() - 1;int len2 = p.size() - 1;//因為在字符串前面加了個'0'，所以字符串的長度 = 字符串的size - 1for (int i = 1/**/, j = 0; i <= len1/*注意是遍歷母串*/; i++){while (j && p[j + 1] != s[i]/*子串的j + 1和母串的i不匹配*/)j = nextt[j];//回退if (p[j + 1] == s[i])//如果匹配上了j++;//繼續往后走，不回退//題目要求的輸出if (j == len2)cout << i - len2 + 1 << endl;}
}void solve()
{string s, p;//母串，子串（模式串）cin >> s >> p;s = '0' + s;//注意下標從1開始p = '0' + p;GetNext(p);KMP(s, p);int len1 = s.size();int len2 = p.size();for (int i = 1/*從1開始*/; i < len2; i++)cout << nextt[i] << " ";cout << endl;
}int main()
{solve();return 0;
}

?