KMP算法用于进行字符串匹配。
暴力的方法是每次失配就从模式串的头部进行匹配，但是因为有前后缀匹配的情况，不必每次回到头部，通过一个next数组, 可以在失配时让主串i去匹配next[j],这样能很快的进行匹配。

如何使用next数组

void KMP(string s, string p)
{int j, i = 0;while(i < p.size()){if(j == -1 || s[j] == p[i])//j == -1 说明第一个字符也不匹配，这样j归0， i增加i ++, j ++;else j = ne[j] //失配则回溯j进行匹配。if(j == s.size())//匹配成功{ans.push_back(i - j);j = ne[j];//回溯j继续匹配。}}
}

如何求解next数组

参考1
参考2
next数组中储存的是这个字符串前缀和后缀中相同字符串的最长长度

如图，next数组中存下了这个字符之前的字符串前后缀的最大公共长度，而j进行回溯也按这个数组。

有这样一个规律，一个串的最小循环节长度：len - next[len]。可以从回溯的角度理解，当匹配完成以后，j会回溯到最后一个循环节进行再次匹配，len减去next[len]就是一个循环节的长度。
一定要注意前提是 len % (len - next[len]) == 0,否则不存在循环周期。

题目

831. KMP字符串

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n, m;
string s, p;
int ne[100010];
vector<int> ans;
void getNext(string s)
{ne[0] = -1;int i = 0, j = -1;//j在前 i在后while(i < s.size()){if(j == -1 || s[i] == s[j]){ne[++ i] = ++ j;// 如果s[i] == s[j] 则 next[i + 1] = next[i] + 1}else j = ne[j];//如果不相等，那么回溯j继续匹配}
}
void KMP(string s, string p)
{int i = 0, j = 0;getNext(s);while(i < p.size()){// cout << i <<" "<< j << endl;if(j == -1 || p[i] == s[j])//第一个就失配，i增加， j归0, 匹配也同时增加  i ++, j ++;else j = ne[j];//回溯jif(j == s.size())//匹配完成{ans.push_back(i - j);j = ne[j];}}
}
int main()
{cin >> n >> s >> m >> p;KMP(s,p);for(auto x : ans){cout << x << " ";}
}