【笔记】前缀函数与KMP算法

这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战.

本期音乐：打上花火 DAOKO/米津玄师

前缀函数

一个字符串s的border是一个最长的字符串，且既是s的后缀，又是s的真前缀。

给定长为n的字符串s，其前缀函数定义为一个长为n的数组

π。其中

π[i]为s的第i个前缀的border长度。

【例子】字符串“abcabcd”的前缀函数为[0,0,0,1,2,3,0]，字符串"aabaaab"的前缀函数为[0,1,0,1,2,2,3].

【练习】写出前缀函数的暴力求法。

复杂度O(n^3)

char save[M];
int prefix_function[M]; //前缀函数，第i个前缀的border长度
int main(void)
{
	scanf("%s",save);
	for(int i=0; save[i]; i++) //第i个前缀
	{
		int &j = prefix_function[i];
		for(j=i; j>=0; --j) //尝试答案为j
		{
			//如果pi[i]=j，意味着s[0,j-1]与s[i-j+1,i]相等
			int suc = 1;
			for(int k=0; k<j; ++k)
			{
				if(save[k]!=save[i-j+1+k])
				{
					suc = 0;
					break;
				}
			}
			if(suc) break;
		}
		printf("%d ",j );
	}

    return 0;
}
复制代码

【笔记】如果

π[i]=j，意味着s[0,j-1]与s[i-j+1,i]相等

高效算法

优化1

结论：

π[i]−π[i−1]<=1

反证法：如果

π[i]=j,π[i+1]=j+2：那么

s[0,j−1]与

s[i−j+1,i]相等，

s[0,j+2]与

s[i−j,i+1]相等。
此时显然

s[0,j+1]与

s[i−j,i]相等，那么

π[i]应该是j+1而不是j，出现矛盾。
两者差值大于2时同理。所以前缀函数后项减前项一定小于等于1.

由此结论，在求

π[i+1]时，可以从

π[i]+1开始向前循环。
【复杂度分析】显然，pi的值最多增加n，也就最多减少n，意味着仅需要n次字符串比较就可以得到所有pi的值，所以此时求前缀函数的复杂度为

O(n2).

优化2

如果

s[i+1]=s[π[i]]，显然

π[i+1]=π[i]+1。

如果两者不相等，我们还需要尝试更小的字符串，为了加速，希望直接移动到一个长度

j<π[i]，且位置i的前缀性质仍然保持，即s[0,j-1] = s[i-j+1...i]。

【笔记】求第i+1个前缀的border时，总是要从第i个前缀的候选border去转移。侯选border为一个子串，且既是真前缀又是后缀，但不一定最长，仍然满足s[0,j-1] = s[i-j+1...i]。

一直重复这个过程，直到j=0为止，此时如果s[0]=s[i+1]，那么pi[i+1]=1，否则为0.

现在只剩下一个问题，如何找到第i个前缀的下一个候选border，即在s[0,j-1]=s[i-j+1]的情况下找到最大的k<j，使得s[0,k-1]=s[i-k+1]。

注意到，s[0,k-1]是s[0,j-1]的真前缀，s[i-k+1]是s[i-j+1]的后缀，也是s[0,j-1]的后缀，所以问题就变成了找到s[0,j-1]的border，即

π[j−1]。

最终算法

1. 
   $\pi[0]=0$

   π[0]=0，从

   $i=1$

   i=1到

   $n-1$

   n−1按如下方式计算

   $\pi[i]$

   π[i]：

2. 为了计算
   $\pi[i]$

   π[i]，定义变量

   $j$

   j表示第i-1个前缀的当前最好的候选border的长度。首先

   $j=\pi[i-1]$

   j=π[i−1]。

3. 比较
   $s[j]和s[i]$

   s[j]和s[i]，如果两者相等，那么

   $\pi[i]=j+1$

   π[i]=j+1，否则

   $j=\pi[j-1]$

   j=π[j−1]并重复该过程。

4. 当
   $j=0$

   j=0时仍失配，令

   $\pi[i]=0$

   π[i]=0。

char save[M];
int prefix_function[M]; //前缀函数，第i个前缀的border长度
int main(void)
{
	scanf("%s",save);
	printf("0\n");
	for(int i=1; save[i]; ++i)
	{
		int j = prefix_function[i-1];
		while(j && save[i]!=save[j]) j=prefix_function[j-1];
		if(save[i]==save[j]) ++j;
		prefix_function[i] = j;

		printf("%d\n",prefix_function[i] );
	}

    return 0;
}
复制代码

此算法不需要进行字符串比较，由优化1可知总操作次数O(n)，而且是在线算法。

应用

单模式匹配

给定文本串t和模式串s，求s在t中的所有出现位置。

构造一个字符串 s + # + t，对其求前缀函数，会发现在t部分的前缀函数的值如果等于|s|，就表示s在其中出现了一次。

这就是KMP算法，很自然吧。
（我终于脱离了会AC自动机但是不会KMP的状态）

找字符串最小周期

【题解】UVA455 找字符串周期 KMP
【题解】UVA11022 String Factoring 字符串周期，区间DP

本文也发表于我的 csdn 博客中。