总算把这个东西搞懂了......
KMP是一个求解字符串匹配问题的算法。
这个东西的核心是一个\(next\)数组，\(next_i\)表示字符串第\(0\sim i\)项的相同的前缀和后缀的最大长度。
这里的前缀和后缀概念略有不同，如 DUCK的前缀为 D,DU,DUC,后缀为 K,CK,UCK，不包含 DUCK本身。
再举一个例子，假设有字符串 DUCKDUCK,则相同的前缀和后缀的最大为 DUCK，因此\(next_7\)值为 \(4\)。
那么怎么求解呢？
对于\(i\),我们知道了\(S_{0\sim next_{i-1}-1}\)和\(S_{i-next_i-1\sim i-1}\)是一样的，如果\(S_{next_{i-1}}=S_i\)就最好，\(next_i=next_{i-1}+1\)。
如果不是怎么办？我们设\(t=next_{i-1}-1\),由于\(S_{0\sim next_{i-1}-1}\)和\(S_{i-next_i-1\sim i-1}\)是一样的，所以在两者的内部，肯定都会有一对长度为\(next_t\)大小的相同的前缀和后缀。
那么，我们考虑新的这个前缀后面等不等于\(s_i\)，等于则问题解决，否则故技重施，再找出一个前缀。
可以手动模拟理解一下。
nxt[0]=-1;
for(int i=1;i<m;i++)
{
t=nxt[i-1];
while(t!=-1&&s2[t+1]!=s2[i])t=nxt[t];//前缀不合法，继续找前缀
if(s2[t+1]==s2[i])nxt[i]=t+1;//终于配上了一个前缀
else nxt[i]=-1;//啥也配不上
}
有了这个\(next\)就方便许多了，我们将短的那个字符串的\(next\)算出，如果匹配失败，可以找出前面的，与后缀一样的部分，顶上来匹配，节省时间。
时间复杂度是\(O(|S|)\)的，也就是\(O(n)\)级别。
int i=0,j=0;
while(i<n)
{
if(s[i]==s2[j])
{
i++,j++;
if(j==m)
{
cout<<i-m+1<<endl;
j=nxt[j-1]+1;
}
}
else
{
if(j==0)i++;
else j=nxt[j-1]+1;
}
}