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

发表于

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

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

前缀函数

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

给定长为n的字符串s，其前缀函数定义为一个长为n的数组π\piπ。其中π[i]\pi[i]π[i]为s的第i个前缀的border长度。

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

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

复杂度O(n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
cpp复制代码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\pi[i]=jπ[i]=j，意味着s[0,j-1]与s[i-j+1,i]相等

高效算法

优化1

结论：π[i]−π[i−1]<=1\pi[i]-\pi[i-1]<=1π[i]−π[i−1]<=1

反证法：如果π[i]=j,π[i+1]=j+2\pi[i]=j,\pi[i+1]=j+2π[i]=j,π[i+1]=j+2：那么s[0,j−1]s[0,j-1]s[0,j−1]与s[i−j+1,i]s[i-j+1,i]s[i−j+1,i]相等，s[0,j+2]s[0,j+2]s[0,j+2]与s[i−j,i+1]s[i-j,i+1]s[i−j,i+1]相等。
此时显然s[0,j+1]s[0,j+1]s[0,j+1]与s[i−j,i]s[i-j,i]s[i−j,i]相等，那么π[i]\pi[i]π[i]应该是j+1而不是j，出现矛盾。
两者差值大于2时同理。所以前缀函数后项减前项一定小于等于1.

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

优化2

如果s[i+1]=s[π[i]]s[i+1]=s[\pi[i]]s[i+1]=s[π[i]]，显然π[i+1]=π[i]+1\pi[i+1]=\pi[i]+1π[i+1]=π[i]+1。

如果两者不相等，我们还需要尝试更小的字符串，为了加速，希望直接移动到一个长度j<π[i]j<\pi[i]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]\pi[j-1]π[j−1]。

最终算法

  1. π[0]=0\pi[0]=0π[0]=0，从i=1i=1i=1到 n−1n-1n−1按如下方式计算π[i]\pi[i]π[i]：
  2. 为了计算π[i]\pi[i]π[i]，定义变量jjj表示第i-1个前缀的当前最好的候选border的长度。首先j=π[i−1]j=\pi[i-1]j=π[i−1]。
  3. 比较s[j]和s[i]s[j]和s[i]s[j]和s[i]，如果两者相等，那么π[i]=j+1\pi[i]=j+1π[i]=j+1，否则j=π[j−1]j=\pi[j-1]j=π[j−1]并重复该过程。
  4. 当j=0j=0j=0时仍失配，令π[i]=0\pi[i]=0π[i]=0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
cpp复制代码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 博客中。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%