【算法入门·字符串】对KMP算法的简单理解

有关KMP算法

$KMP$KMP算法通俗的说，就是一个字符串$A$A，一个字符串$B$B，$A$A的长度小于$B$B，可以求$A$A是否是$B$B的子串；若$A$A是$B$B的子串，甚至还可以求出$A$A在$B$B中在不同位置里的出现次数。

若$A$A的长度为$N$N，$B$B的长度为$M$M，则双重循环暴力匹配的算法的时间复杂度是$O(NM)$O(NM),这显然对于$KMP$KMP的$O(N+M)$O(N+M)的复杂度有所差异，而$KMP$KMP可以在快速的时间内求解这个问题。
（这里会强调一些我之前听挂的内容，所以语言很通俗，不要介意啦）

有关KMP前缀的next数组解法

我们规定$next[i]$next[i]表示在$A$A串中长度为$[1...i]$[1...i]的子串中，靠前和靠后的最大相同子串的长度。

例如，字符串$ABCD$ABCD中，靠前的表示：$A，AB，ABC$A，AB，ABC，表示一定要挨着第一个字母$A$A。

同样，靠后的就是$D，CD，BCD。$D，CD，BCD。

有例如，在字符串$ACDAB$ACDAB中，$AB$AB既满足靠前的，也满足靠后的；我们把这样的字符串的最大长度称为$next$next数组的值。

然后，我们在求解$next[i]$next[i]的时候，就可以用递推的思想，即如何根据已知$next[1-(i-1)]$next[1−(i−1)]来求。

最暴力的方法就是双重循环进行自我匹配，这显然不可取；我们举一个例子来理解一下吧。

再来个例子，$ABCABA。$ABCABA。

$step1：$step1：匹配$ABC$ABC，匹配不到；$next[1-3]=0.$next[1−3]=0.

$step2：$step2：匹配第四个$A$A，此时可以和第一个$A$A进行匹配，则$next[4]=1.$next[4]=1.

$step3：$step3：匹配第五个$B$B，此时可以和第二个$B$B进行匹配，则$next[5]=2.$next[5]=2.

关键的step4： 匹配第六个$D$D时，发现第三个$C$C不匹配；此时另一个指针指向的时$3$3（主指针指向的时6），此时要重新再前面找到一个子串$A[1...j]且j&lt;2和A[k...6]且k&gt;4$A[1...j]且j<2和A[k...6]且k>4进行匹配；此时我们会发现$A[1...j]=A[k...6]$A[1...j]=A[k...6];此时由于$A[1..2]$A[1..2]和$A[4..5]$A[4..5]是匹配的，所以$A[k...6]=A[p...2],$A[k...6]=A[p...2],此时$A[1...j]=A[p...2]$A[1...j]=A[p...2]，那么其实就是上面的$next$next数组的含义，前面的和后面的最大长度的字符串。

如果你还是不理解，我们画个图吧。

然后就上代码了：

for (int i=2,j=0;i<=n;++i)
		{
			while (j>0 && a[i]!=a[j+1]) j=next[j];
			if (a[i]==a[j+1]) j++;
			next[i]=j;
		}

关于两个不同的字符进行匹配

好吧思路其实和上面一样；唯一有一个不通电就是，当指针j=n时表示已经匹配完了，此时我们需要进行j=next[j]操作并统计答案。

现在给出一个给定一个字符串 A 和一个字符串 B，求 B 在 A 中的出现次数 这道题的模板。

#include<bits/stdc++.h>
using namespace std;
int ans=0;
char a[2000000];
char b[2000000];
int next[2000000];
int main(void)
{
	freopen("kmp.in","r",stdin);
	freopen("kmp.out","w",stdout);
	cin>>a+1>>b+1;
	int len1=strlen(a+1);
	int len2=strlen(b+1);
	for (int i=2,j=0;i<=len2;++i)
	{
		while (j>0 && b[i]!=b[j+1]) j=next[j];
		if (b[i]==b[j+1]) j++;
		next[i]=j;
	}
	for (int i=1,j=0;i<=len1;++i)
	{
		while (j>0 && a[i]!=b[j+1]) j=next[j];
		if (a[i]==b[j+1]) j++;
		if (j==len2) ans++,j=next[j];
	}
	cout<<ans<<endl;
	return 0;
} 

KMP例题[Usaco2015 Feb]Censoring

这道题就是一个KMP模版的变式，因为中间要不断删除，两边会产生连接，这正好符合栈这一个数据结构。

因为按照KMP的算法来，算一个进栈一个；如果匹配了，则弹出所有匹配的字符串，继续在栈上面进行匹配；这样，既能够进行正常的KMP匹配算法，还可以进行删除和拼接的操作。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int top=0;
int s[2000000];
int f[2000000];
char a[2000000];
char b[2000000];
int next[2000000];
int main(void)
{
	freopen("censor.in","r",stdin);
	freopen("censor.out","w",stdout);
	cin>>a+1>>b+1;
	int len1=strlen(a+1);
	int len2=strlen(b+1);
	for (int i=2,j=0;i<=len2;++i)
	{
		while (j>0 && b[i]!=b[j+1]) j=next[j];
		if (b[i]==b[j+1]) j++;
		next[i]=j;
	}
	for (int i=1,j=0;i<=len1;++i)
	{
		while (j>0 && a[i]!=b[j+1]) j=next[j];
		if (a[i]==b[j+1]) j++;
		f[i]=j;
		s[++top]=i;
		if (f[i]==len2)
		{
			top-=len2;
			j=f[s[top]];
		} 
	}
	for (int i=1;i<=top;++i) cout<<a[s[i]];
	return 0;
}