KMP 学习笔记

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

对于长度分别为 $n,m$ 的字符串 $S,T$，显然可以暴力地找到 $T$ 在 $S$ 中的所有出现位置：

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)$ 的。

考虑改进这个算法，注意到下面这两个字符串匹配时：

S:ACACBEAC

T:ACACE

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

S:ACACBEEAC

T:^^ACACE

因为 $T_{[1,4]}$ 已经匹配了，而在 $T_{[1,4]}$ 中，前两位构成的前缀 $T_{[1,2]}$ 和后两位构成的后缀 $T_{[3,4]}$ 相同，所以可以移动两位。

对于一个字符串 $S$，定义 $b$ 为 $S$ 的 border 当且仅当 $1\le b< |S|$ 且 $S_{[1,|b|]}=S_{[|S|-b+1,|S|]}$。那么当 $T$ 的前 $j$ 位已匹配，第 $j+1$ 位失配时，就可以将 $j$ 设置成 $T_{[1,j]}$ 的最长的 border 的长度。

设 $kmp_i$ 表示 $T_{[1,i]}$ 的最长 border 的长度，那么匹配的过程就可以变成这样：

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

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

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

这样做的时间复杂度是 $O(n+m)$ 的。

时间复杂度证明：

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

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

实际上 $kmp$ 数组相当于单串 AC 自动机的 $fail$ 数组。

一些拓展

• 想要求 $T_{[1,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$ 表示 $a_{[1,i]}$ 长度小于等于 $\lfloor\frac{i}{2}\rfloor$ 的最长的 border 的长度。

  这样做的时间复杂度是 $O(n)$ 的，证明类似求 $kmp$ 数组的时间复杂度的证明。

• 一些字符串的定理