总算把这个东西搞懂了......

KMP是一个求解字符串匹配问题的算法。

这个东西的核心是一个nextnext数组，nextinext_i表示字符串第0∼i0\sim i项的相同的前缀和后缀的最大长度。

这里的前缀和后缀概念略有不同，如 DUCK的前缀为 D,DU,DUC,后缀为 K,CK,UCK，不包含 DUCK本身。

再举一个例子，假设有字符串 DUCKDUCK,则相同的前缀和后缀的最大为 DUCK，因此next7next_7值为 44。

那么怎么求解呢？

对于ii,我们知道了S0∼nexti−1−1S_{0\sim next_{i-1}-1}和Si−nexti−1∼i−1S_{i-next_i-1\sim i-1}是一样的，如果Snexti−1=SiS_{next_{i-1}}=S_i就最好，nexti=nexti−1+1next_i=next_{i-1}+1。

如果不是怎么办？我们设t=nexti−1−1t=next_{i-1}-1,由于S0∼nexti−1−1S_{0\sim next_{i-1}-1}和Si−nexti−1∼i−1S_{i-next_i-1\sim i-1}是一样的，所以在两者的内部，肯定都会有一对长度为nexttnext_t大小的相同的前缀和后缀。

那么，我们考虑新的这个前缀后面等不等于sis_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;//啥也配不上
}

有了这个nextnext就方便许多了，我们将短的那个字符串的nextnext算出，如果匹配失败，可以找出前面的，与后缀一样的部分，顶上来匹配，节省时间。

时间复杂度是O(∣S∣)O(|S|)的，也就是O(n)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;
	}
}