[算法] 前缀函数与KMP算法

前缀函数

前缀函数 $nxt[i]$定义为 子串$s[1\dots i]$最长的相等的真前缀与真后缀的长度。

计算前缀函数

	scanf("%s",b+1);
	lb=strlen(b+1);
	int j=0;nxt[1]=0;
	for(int i=2;i<=lb;i++){
		while(j&&b[j+1]!=b[i]) j=nxt[j];
		if(b[j+1]==b[i]) j++;
		nxt[i]=j;
	}

在线算法，时间复杂度$O(n)$

应用

[KMP算法] 给定一个模式串和一个待匹配串，找出前者在后者中的所有位置

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
char a[maxn],b[maxn];
int la,lb,next[maxn];
int main(){
	scanf("%s%s",a+1,b+1);
	la=strlen(a+1);
	lb=strlen(b+1);
	int j=0;
	for(int i=2;i<=lb;i++){
		while(j&&b[j+1]!=b[i]) j=next[j];
		if(b[j+1]==b[i]) j++;
		next[i]=j;
	}
	j=0;
	for(int i=1;i<=la;i++){
		while(j&&b[j+1]!=a[i]) j=next[j];
		if(b[j+1]==a[i]) j++;
		if(j==lb){
			printf("%d\n",i-lb+1);
			j=next[j];
		}
	}
	for(int i=1;i<=lb;i++){
		printf("%d ",next[i]);
	}
	return 0;
}

//把模式串与待匹配串接在一起，一次解决
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
char a[maxn],b[maxn],c[maxn<<1];
int la,lb,lc,nxt[maxn<<1];
int main(){
	scanf("%s%s",a+1,b+1);
	la=strlen(a+1);
	lb=strlen(b+1);
	lc=0;
	for(int i=1;i<=lb;i++) c[++lc]=b[i];//b是模式串 
	c[++lc]='#';
	for(int i=1;i<=la;i++) c[++lc]=a[i];//a是待匹配串 
	int j=0;nxt[1]=0;
	for(int i=2;i<=lc;i++){
		while(j&&c[j+1]!=c[i]) j=nxt[j];
		if(c[j+1]==c[i]) j++;
		nxt[i]=j;
		if(i>lb+1){
			if(nxt[i]==lb) printf("%d\n",(i-lb-1)-lb+1);
		} 
	}
	for(int i=1;i<=lb;i++){
		printf("%d ",nxt[i]);
	}
	return 0;
}

找字符串的所有周期

字符串的周期：对字符串 $s$ 和 $0<p\le |s|$，若 $s[i]=s[i+p]$ 对所有 $i\in [1,|s|-p]$ 成立，则称 $p$ 是 $s$ 的周期。

字符串的$border$：对字符串 $s$ 和 $0\le r<|s|$，若 $s$ 长度为 $r$ 的前缀和长度为 $r$ 的后缀相等，就称 $s$ 长度为 $r$ 的前缀是 $s$ 的 $border$。

由 $s$ 有长度为 $r$ 的 $border$ 可以推导出 $|s|-r$ 是 $s$ 的周期。

由 $nxt[i]$ ，可以得到 $s$ 所有的 $border$ 长度，即 $nxt[n],nxt[nxt[n]],\dots$，由此可以得出 $s$ 所有的周期。
其中最小正周期为 $|s|-nxt[n]$。

统计模式串每个前缀的出现次数

问题一： 统计每个前缀 $s[1\dots i]$ 在同一个字符串 $s$ 的出现次数

以位置 $i$ 为右端点，有长度为 $nxt[i]$ 的前缀，有长度为 $nxt[nxt[i]]$ 的前缀，有长度为 $nxt[nxt[nxt[i]]]$ 的前缀，等等，直到长度变为 0。

for(int i=1;i<=n;i++) cnt[nxt[i]]++;
for(int i=n;i>=1;i--) cnt[nxt[i]]+=cnt[i];
for(int i=1;i<=n;i++) cnt[i]++;//加上前缀自身

问题二： 统计每个前缀 $s[1\dots i]$ 在另一个字符串 $t$ 的出现次数

构造 $s[1\dots n]$#$t[1\dots m]$

	scanf("%s%s",a+1,b+1);
	la=strlen(a+1);
	lb=strlen(b+1);
	lc=0;
	for(int i=1;i<=lb;i++) c[++lc]=b[i];//b是模式串 
	c[++lc]='#';
	for(int i=1;i<=la;i++) c[++lc]=a[i];//a是待匹配串 
	int j=0;nxt[1]=0;
	for(int i=2;i<=lc;i++){
		while(j&&c[j+1]!=c[i]) j=nxt[j];
		if(c[j+1]==c[i]) j++;
		nxt[i]=j;
	}
	for(int i=lb+2;i<=lc;i++) cnt[nxt[i]]++;
	for(int i=lb;i>=1;i--) cnt[nxt[i]]+=cnt[i];
	for(int i=1;i<=lb;i++) 
		printf("%d ",cnt[i]);

一个字符串中本质不同子串的数目

令 $k$ 为当前 $s$ 的本质不同子串数量，当前 $s$ 的长度为 $n$ 。
我们添加一个新的字符 $c$ 至 $s$ 末尾。
显然，会有一些新的子串以字符 $c$ 结尾。我们希望对这些以该字符结尾且我们之前未曾遇到的子串计数。

构造字符串 $t=s[1\dots n]c$ 并将其反转得到字符串 $t^{\sim }$。
现在我们的任务变为计算有多少 $t^{\sim }$ 的前缀未在 $t^{\sim }$ 的其余任何地方出现。
如果我们计算了 $t^{\sim }$ 的前缀函数最大值 $nx{t}_{\max }$，那么出现在 $s^{\sim }$ 中的 $t^{\sim }$ 前缀的最长长度为 $nx{t}_{\max }$。自然的，所有更短的前缀也出现了。

因此，当添加了一个新字符后新出现的子串数目为 $|s|+1-nx{t}_{\max }$。

所以对于每个添加的字符，我们可以在 $O(n)$ 的时间内计算新子串的数目，故最终复杂度为 $O(n^2)$。

值得注意的是，我们也可以重新计算在头部添加一个字符，或者从尾或者头移除一个字符时的本质不同子串数目。

字符串压缩

给定一个长度为 $n$ 的字符串 $s$，我们希望找到其最短的「压缩」表示，也即我们希望寻找一个最短的字符串 $t$，使得 $s$ 可以被 $t$ 的一份或多份拷贝的拼接表示。

让我们计算 $s$ 的前缀函数。通过使用该函数的最后一个值 $nxt[n-1]$，我们定义值 $k=n-nxt[n-1]$。我们将证明，如果 $k$ 整除 $n$，那么 $k$ 就是答案，否则不存在一个有效的压缩，故答案为 $n$。

假定 $n$ 可被 $k$ 整除。那么字符串可被划分为长度为 $k$ 的若干块。根据前缀函数的定义，该字符串长度为 $n-k$ 的前缀等于其后缀。但是这意味着最后一个块同倒数第二个块相等，并且倒数第二个块同倒数第三个块相等，等等。作为其结果，所有块都是相等的，因此我们可以将字符串 $s$ 压缩至长度 $k$。
诚然，我们仍需证明该值为最优解。实际上，如果有一个比 $k$ 更小的压缩表示，那么前缀函数的最后一个值 $nxt[n-1]$ 必定比 $n-k$ 要大。因此 $k$ 就是答案。

现在假设 $n$ 不可以被 k 整除，我们将通过反证法证明这意味着答案为 $n$。假设其最小压缩表示 $r$ 的长度为 $p$（$p$ 整除 $n$），字符串 $s$ 被划分为 $n/p\ge 2$ 块。那么前缀函数的最后一个值 $nxt[n-1]$ 必定大于 $n-p$（如果等于则 $n$ 可被 $k$ 整除），也即其所表示的后缀将部分的覆盖第一个块。现在考虑字符串的第二个块。该块有两种解释：第一种为 $r_0{r}_1\dots r_{p-1}$，另一种为$r_{p-k}{r}_{p-k+1}\dots r_{p-1}{r}_0{r}_1\dots r_{p-k-1}$。由于两种解释对应同一个字符串，因此可得到 $p$ 个方程组成的方程组，该方程组可简写为 $r_{(i+k)\mathrm{mod}p}=r_{i\mathrm{mod}p}$。
$\begin{array}{c}\stackrel{nxt[n-1]}{\overbrace{r_0{r}_1{r}_2\dots r_{k-1}{r}_k\dots r_{p-1}{r}_0{r}_1{r}_2\dots r_{p-1-k}}}{r}_{p-k}\dots r_{p-1}\\ r_0{r}_1\dots r_{p-1-k}\underset{p}{\underbrace{r_{p-k}\dots r_{p-1}{r}_0{r}_1{r}_2\dots r_{p-1-k}}}{r}_{p-k}\dots r_{p-1}\\ r_0{r}_1{r}_2\dots r_{k-1}\underset{nxt[n-1]}{\underbrace{r_k\dots r_{p-1}{r}_0{r}_1{r}_2\dots r_{p-1-k}{r}_{p-k}\dots r_{p-1}}}\end{array}$
根据扩展欧几里得算法我们可以得到一组 $x$ 和 $y$ 使得 $xk+yp=\gcd (k,p)$。通过与等式 $pk-kp=0$ 适当叠加我们可以得到一组 $x^{\prime }>0和y^{\prime }<0$ 使得 $x^{\prime }k+y^{\prime }p=\gcd (k,p)$。这意味着通过不断应用前述方程组中的方程我们可以得到新的方程组 $r_{(i+\gcd (k,p))\mathrm{mod}p}=r_{i\mathrm{mod}p}$。
由于 $\gcd (k,p)$ 整除 $p$，这意味着 $\gcd (k,p)$ 是 $r$ 的一个周期。又因为 $nxt[n-1]>n-p$，故有 $n-nxt[n-1]=k<p$，所以 $\gcd (k,p)$ 是一个比 $p$ 更小的 $r$ 的周期。因此字符串 $s$ 有一个长度为 $\gcd (k,p)<p$ 的压缩表示，同 $p$ 的最小性矛盾。