KMP算法

一.引入(洛谷 P3375)

给出两个字符串 \(s_1\) 和 \(s_2\)，若 \(s_1\) 的区间 \([l, r]\) 子串与 \(s_2\) 完全相同，则称 \(s_2\) 在 \(s_1\) 中出现了，其出现位置为 \(l\)。
现在请你求出 \(s_2\) 在 \(s_1\) 中所有出现的位置。
\(s1\)称为文本串，\(s2\)称为模板链

二.简陋版本

不难想到，用两个\(for\)一个位置一个位置比对即可，复杂度为\(O(n*m)\)

三.KMP算法

为了省去那些无谓的比对，KMP算法应运而生。

1.最长相等前后缀

例如\(ABBABB\),其最长相等前后缀就是\(ABB\)

2.核心思想

在安位比对之后，若遇到此位模板串和文本串不同时，可以通过最长相等前后缀将模板串的头拉到当前位置，如

       
文本串：abcacababcab
模板串：abcab(调整前)
模板串：   abcab(调整后)

对于第五个位置两者不一样，对于\(abca\)，最长相等前后缀是\(a\),于是将模板串调整到相应位置，省去了很多比较

3.正确性

如此比较我们不会漏掉任何一个答案，任何答案不会藏在调整前和调整后中间的状态，下面用反证法证明：

如下特殊形式，X代表此位二者不同，只有遇到不同位时才需要调整，意味着X以前全一样
文本串：AB ··· AB ··· AB ···
              1      2
模板串：AB ··· AB ··· AB X···
              3      4
比对到X位置时，我们开始调整，如果说此时最长相等前后缀为AB，则正确情况为：
文本串：AB ··· AB ··· AB ···
模板串：              AB ··· AB ··· AB X···
如果我们在中间有遗漏可能匹配成功，即如下情况可能成功：
文本串：AB ··· AB ··· AB ···
              5      6
模板串：       AB ··· AB ··· AB X···
              7      8      9
1~2与3~4一样，若上述情况成功匹配，则5~6与7~8相同，则7~8与8~9相同，最长相等前后缀应为7~8,与上文所说AB相矛盾，得证

四.代码讲解

这种感觉更像是抽动模板串的操作

1.\(kmp[N]\)

\(kmp[k]\)代表对于1~\(k\)这段的最长相等前后缀长度

2.匹配

	j=0;//理解为目前模板串比较到哪一位了
	for(int i=1;i<=l1;i++)
	{
		while(j&&s1[i]!=s2[j+1])//若j=0但s1[i]==s2[j+1]不就死循环了吗
		                        //循环找到可能成功的情况，都s1[i]!=s2[j+1]了
		                        //肯定不会成功啊
			j=kmp[j];//模板串调整到kmp[j]位置，再安放到对应文本串位置
		if(s1[i]==s2[j+1])
			j++;//模板链继续向后拓展
		if(j==l2)//匹配成功
		{
			cout<<i-l2+1<<endl;
			j=kmp[j];//继续新一轮匹配，可能多解
		}
	}

3.\(kmp[N]\)求解

\(kmp[0]=kmp[1]=0\),因为前缀后缀都不包括自身
考虑将模板串与自身比对，如：

文本串：ABABAC
模板串：  ABABAC
对于不同的C-B，即第六位，ABA刚好就是前五位构成串的最长相等前后缀，很好理解

int j=0;
for(int i=2;i<=l2;i++)
	{
		while(j&&s2[i]!=s2[j+1])
			j=kmp[j];
		if(s2[i]==s2[j+1])
			j++;
		kmp[i]=j;
	}

4.AC代码

#include<bits/stdc++.h>
using namespace std;
const int  N=1e6+10;
int kmp[N],l1,l2,j;
char s1[N],s2[N];
int main()
{
	scanf("%s",s1+1);
	scanf("%s",s2+1);
	l1=strlen(s1+1);
	l2=strlen(s2+1);
	for(int i=2;i<=l2;i++)
	{
		while(j&&s2[i]!=s2[j+1])
			j=kmp[j];
		if(s2[i]==s2[j+1])
			j++;
		kmp[i]=j;
	}
	j=0;
	for(int i=1;i<=l1;i++)
	{
		while(j&&s1[i]!=s2[j+1])
			j=kmp[j];
		if(s1[i]==s2[j+1])
			j++;
		if(j==l2)
		{
			cout<<i-l2+1<<endl;
			j=kmp[j];
		}
	}
	for(int i=1;i<=l2;i++)
		cout<<kmp[i]<<" ";
	return 0;
}

5.时间复杂度

\(O(N+M)\),看不懂咋证的，逃（