KMP 学习笔记

KMP 是一种用来处理字符串匹配问题的算法。

很明显，可以这样暴力解决字符串匹配问题：（ $n$ 为 $S$ 的长度， $m$ 为 $T$ 的长度）

for(int i=1;i<=n-m+1;i++)
{
	bool f=true;
	for(int j=1;j<=m;j++)
	{
		if(S[i+j-1]!=T[j])
		{
			f=false;
			break;
		}
	}
	if(f)
	{
		printf("%d\n",i);
	}
}

但是这样的算法时间复杂度是 $O(nm)$ 的，肯定会 TLE。

考虑改进这个算法，很容易发现，下面这两个字符串匹配时：

S:ACACBEAC

T:ACACE

模式串匹配到 E 时我们发现失配了，但是这时我们可以不仅仅把 $T$ 移动一位，而是可以直接移动两位：

S:ACACBEEAC

T:^^ACACE

因为 $T$ 的前四位已经匹配了，而在这前四位中，前两位构成的前缀和后两位构成的后缀相同，所以我们可以移动两位。

设 $frt_j$ 表示 $T$ 的前 $j$ 个字符构成的字符串，定义一个串 $S$ 的 border $T$ 为满足 $T\not=S$ 且既是 $S$ 的前缀也是 $S$ 的后缀的串。那么当 $T$ 的前 $j$ 位已匹配，第 $j+1$ 位失配时，就可以将 $j$ 设置成 $frt_j$ 的最长的 border 的长度。

那么我们可以用 $kmp_i$ 表示 $frt_i$ 的最长 border 的长度，那么匹配的过程就可以变成这样：

int j=0;
for(int i=1;i<=n;i++)
{
	while(j!=0&&T[j+1]!=S[i]) // 如果失配，那么不停移动模式串 
	{
		j=kmp[j];
	}
	if(T[j+1]==S[i]) // 能匹配就匹配 
	{
		j++;
	}
	if(j==m) // 匹配成功！ 
	{
		printf("%d\n",i-m+1);
	}
}

而 $kmp$ 数组的求解就可以看作是 $T$ 和自己匹配：

kmp[1]=0; // kmp[1] 肯定为 0 
int j=0;
for(int i=2;i<=m;i++) // T 和自己匹配 
{
	while(j!=0&&T[j+1]!=T[i]) // 失配则不断移动模式串 
	{
		j=kmp[j];
	}
	if(T[j+1]==T[i]) // 匹配 
	{
		j++;
	}
	kmp[i]=j; // 当前匹配的长度就是 kmp[i] 
}

完整代码：

// P3375
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n,m;
char S[1000005],T[1000005];
int kmp[1000005];

int main()
{
	scanf("%s%s",S+1,T+1);
	n=strlen(S+1);
	m=strlen(T+1);
	kmp[1]=0; // kmp[1] 肯定为 0 
	int j=0;
	for(int i=2;i<=m;i++) // T 和自己匹配 
	{
		while(j!=0&&T[j+1]!=T[i]) // 失配则不断移动模式串 
		{
			j=kmp[j];
		}
		if(T[j+1]==T[i]) // 匹配 
		{
			j++;
		}
		kmp[i]=j; // 当前匹配的长度就是 kmp[i] 
	}
	j=0;
	for(int i=1;i<=n;i++)
	{
		while(j!=0&&T[j+1]!=S[i]) // 如果失配，那么不停移动模式串 
		{
			j=kmp[j];
		}
		if(T[j+1]==S[i]) // 能匹配就匹配 
		{
			j++;
		}
		if(j==m) // 匹配成功！ 
		{
			printf("%d\n",i-m+1);
		}
	}
	for(int i=1;i<=m;i++)
	{
		printf("%d ",kmp[i]);
	}
	printf("\n");
	return 0;
}

这样做的时间复杂度是 $O(n+m)$ 的，是不是比暴力优很多。

时间复杂度证明：

首先预处理 $kmp$ 数组是 $O(m)$ 的，因为 $j$ 总共只会移动 $m$ 次，然后每次跳 $kmp$ 至少会让 $j$ 减少 $1$ ，所以最多回跳 $m$ 次。

匹配的时间复杂度是 $O(n)$ 的，具体原理同上。

一些扩展

$frt_i$ 的 border 一定是 $frt_{kmp_i},frt_{kmp_{kmp_i}},frt_{kmp_{kmp_{kmp_i}}},\dots$ ，所以可以建一棵根节点为 $0$ 的树，其中 $u$ 的父亲是 $kmp_u$ ， $u$ 的所有祖先 $rt$ 的 $frt_{rt}$ 都是 $frt_u$ 的 border。
想要求 $frt_i$ 长度小于等于 $i-x$ 或者 $\lfloor\frac{i}{x}\rfloor$ 的最长的 border 也可以用类似求 $kmp$ 数组的方法来求：
```
num[1]=0; 
for(int i=2,j=0;i<=n;i++)
{
	while(j!=0&&a[j+1]!=a[i]) j=kmp[j];
	if(a[j+1]==a[i]) j++;
	while(j*2>i) j=kmp[j];
	num[i]=j;
}
```
这段代码就是求 $num_i$ 表示 $frt_i$ 长度小于等于 $\lfloor\frac{i}{2}\rfloor$ 的最长的 border 的长度。

这样做的时间复杂度是 $O(n)$ 的，证明类似求 $kmp$ 数组的时间复杂度的证明。
字符串 $S$ 的最小重复子串（最短的字符串 $B$ 满足 $S=BBBBB\dots BB$ ）也能用 $kmp$ 数组求，若 $kmp_{|S|}\ge\lceil\frac{|S|}{2}\rceil$ 则最小重复子串的长度即为 $|S|-kmp_{|S|}$ ，否则 $S$ 的最小重复子串就是它本身。

证明很简单。

一些扩展

感谢您的支持，我会继续努力的!