kmp
以前觉得好难，现在感觉好简单。再次梳理一下。
首先构造next数组用来代表前缀重复最大的长度。如果prelen和i的字符相等那么直接next[i]=prelen+1,同时i和prelen递增；如果不相等，prelen是0直接加入0；如果不是0,那么取next[prelen-1]也就是避免重复比较。然后是正式比较，如果s[i]==p[j]那么说明相等，i和j自增即可；如果不相等，但是j是0说明一开始就不同，直接i++；如果j不是0说明有比较的那么j=next[j-1]避免重复比较。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;int main()
{int n,m;string p,s;cin >> n >> p >> m >> s;vector<int> next(n,0);//构造nextnext[0] = 0;//初始化第一个为0int prelen = 0;int i = 1;while(i<n){if(p[i]==p[prelen])next[i++]=++prelen;//比较相等那么next为prelen+1,i自增else if(prelen==0)next[i++]=0; //如果是0直接纳入，i自增else prelen = next[prelen-1]; //不是0,取其前缀继续}//比较int j = 0;i = 0;vector<int>res;while(i<m){if(s[i]==p[j]){i++;j++;}//相等二者共同增加else if(j>0) j=next[j-1];//不相等，j大于0那么取前缀else i++;//直接不等，直接增加if(j==n){res.push_back(i-j);j=next[j-1];}//如果达到长度则记录并且更新j}for(int x:res)cout << x << " ";return 0;
}