【瞎口胡】KMP 算法

从暴力算法到 KMP
$\operatorname{maxlen}[]$ 的求法
$\operatorname{next}[]$ 的求法及算法主体
例题
- 例题 1 Luogu P3375【模板】KMP字符串匹配
- 例题 2 [NOI2014]动物园

KMP 算法是一种字符串匹配算法。

从暴力算法到 KMP

问题：询问字符串 $S$ 在 $T$ 中出现了多少次。

当 $S=\texttt{abc},T=\texttt{abcfcabcbabc}$ 时，$S$ 在 $T$ 中出现了 $3$ 次 —— $\color{red}{\texttt{abc}}\color{black}{\texttt{f}}\color{red}{\texttt{abc}}\color{black}{\texttt{b}}\color{red}{\texttt{abc}}$。

而当 $S=\texttt{aba},T=\texttt{abababa}$ 时，$S$ 在 $T$ 中出现了 $4$ 次。

考虑暴力算法，枚举每一个可能的位置，并匹配。设 $S$ 的长度为 $m$，$T$ 的长度为 $n$，则总复杂度为 $O(n\times m)$。

我们发现，暴力的效率之所以低，是因为枚举位置时，总是从头开始匹配。每次失配，$S$ 和 $T$ 的下标都会回退。

能不能仅仅回退 $S$ 的下标呢？答案是肯定的。

考虑 $S = \texttt{abeabc},T=\texttt{abeabeabc}$ 这一组数据。

在匹配时，我们用绿色表示匹配成功，黄色表示正在匹配，红色表示失配，黑色表示还未匹配。

$\color{green}{\texttt{abeab}}\color{black}{\texttt{c}}$ $\color{green}{\texttt{abeab}}\color{black}{\texttt{eabc}}$

$S$ 和 $T$ 的前 $5$ 个字符是匹配的。
$\color{green}{\texttt{abeab}}\color{yellow}{\texttt{c}}$ $\color{green}{\texttt{abeab}}\color{yellow}{\texttt{e}}\color{black}{\texttt{abc}}$

现在匹配第 $6$ 个字符。
$\color{green}{\texttt{abeab}}\color{red}{\texttt{c}}$ $\color{green}{\texttt{abeab}}\color{red}{\texttt{e}}\color{black}{\texttt{abc}}$

我们发现，第 $6$ 个字符失配了。注意到已经匹配了的一段 $\color{green}{\texttt{abeab}}$ 中，存在一个相等的前后缀 $\color{green}{\texttt{ab}}$，我们不重头开始匹配，而是保留匹配的前后缀 $\color{green}{\texttt{ab}}$，然后继续匹配，如下。
- $\color{green}{\texttt{ab}}\color{yellow}{\texttt{e}}\color{black}{\texttt{abc}}$ $\color{red}{\texttt{abe}}\color{green}{\texttt{ab}}\color{yellow}{\texttt{e}}\color{black}{\texttt{abc}}$
$\color{green}{\texttt{ab}}\color{green}{\texttt{e}}\color{green}{\texttt{abc}}$ $\color{red}{\texttt{abe}}\color{green}{\texttt{ab}}\color{green}{\texttt{e}}\color{green}{\texttt{abc}}$

所以我们发现，当 $S[0,i]$ 的一个真前缀（与串本身不相等）和其等长后缀相等时，可以从后缀跳回这个前缀开始匹配。

$\operatorname{maxlen}[]$ 的求法

设 $\operatorname{maxlen}_i$ 表示 $S[0,i]$ 中最长的相等真前后缀。运用上文中「从后缀退回前缀」的思想，容易得到以下代码：

inline void get_next(void){
	int i=1,len=0;
	while(i<lenb){
		if(B[i]==B[len]){ // 如果当前位置匹配成功
			maxlen[i++]=++len;
		}else{
			if(len>0){ // 跳回真前缀继续匹配
				len=maxlen[len-1];
			}else{ // 没有可以跳的真前缀了 maxlen[i] 就是 0
				maxlen[i++]=len;
			}
		}
	}
	return;
}

$\operatorname{next}[]$ 的求法及算法主体

设 $\operatorname{next}_i$ 表示在位置 $i$ 失配，应该跳转到哪里。显然在位置 $0$ 失配无法跳转，只能从下一个位置开始匹配，记为 $-1$。

否则 $\operatorname{next}_i=\operatorname{maxlen}_{i-1}$，因为 $S[0,i-1]$ 都是匹配的，可以用上面的方法跳到前缀。

// KMP 算法本体：输出所有匹配的位置
// 因为 next 作为变量名在 C++11 及以上标准会 CE，代码中均替换为 nex
inline void KMP(void){
	int i=0,j=0;
	nex[0]=-1;
	for(rr int i=1;i<lenb;++i)
		nex[i]=maxlen[i-1];
	while(i<lena){
		if(j==lenb-1&&A[i]==B[j]){
			printf("%d\n",i-j); // 这里是下标从 0 开始的情况
			j=nex[j]; // 当匹配成功时，仍然可以跳 next
			if(j==-1) // 特判 next 为 -1 的情况
				++j;
		}
		if(A[i]==B[j]){
			++i;
			++j;
		}else{
			j=nex[j];
			if(j==-1)
				++i,++j;
		}
	}
	return; 
}

因为 $i$ 最多移动 $n$ 次，所以 $j$ 最多增加 $n$ 次，从而最多减少 $n$ 次，总复杂度为 $O(n)$。

例题

例题 1 Luogu P3375【模板】KMP字符串匹配

题意

给定字符串 $s_1,s_2$，下标范围从 $1$ 开始。求 $s_2$ 在 $s_1$ 中出现了多少次，并要求额外输出 $\operatorname{maxlen}$ 数组。

字符串 $a$ 在 $b$ 中出现次数即满足 $b[l,r] = a$ 的区间 $[l,r]$ 的数量。

\[1 \leq |s_1|,|s_2| \leq 10^6 \]

题解

模板题。

注意下标范围从 $1$ 开始，只需要在 KMP() 中略作修改。

# include <bits/stdc++.h>
const int N=1000010;
char A[N],B[N];
int lena,lenb;
int maxlen[N],next[N];
inline void get_next(void){
	int i=1,len=0;
	while(i<lenb){
		if(B[i]==B[len]){
			maxlen[i++]=++len;
		}else{
			if(len>0){
				len=maxlen[len-1];
			}else{
				maxlen[i++]=len;
			}
		}
	}
	return;
}
inline void KMP(void){
	int i=0,j=0;
	next[0]=-1;
	for(int i=1;i<lenb;++i)
		next[i]=maxlen[i-1];
	while(i<lena){
		if(j==lenb-1&&A[i]==B[j]){
			printf("%d\n",i-j+1),j=next[j]; // 这里加上 1 即可
			if(j==-1)
				++j;
		}
		if(A[i]==B[j]){
			++i,++j;
		}else{
			j=next[j];
			if(j==-1)
				++i,++j;
		}
	}
	return; 
}
int main(void){
	scanf("%s",A),scanf("%s",B);
	lena=strlen(A),lenb=strlen(B);
	get_next();
	KMP();
	for(int i=0;i<lenb;++i)
		printf("%d ",maxlen[i]);
	return 0;
}

例题 2 [NOI2014]动物园

题意

对于字符串 $s = s[1 \cdots n]$，定义 $\operatorname{num}_i$ 为 $s[1...i]$ 的前缀中，与自己等长后缀相等且两者不重叠的前缀数量。

对于 $s = \texttt{abcabca}$，$\operatorname{num}_5 = 2$，满足条件的前缀为 $\texttt{a},\texttt{ab}$。注意 $\operatorname{num}_7 = 1$ 而不是 $2$，因为 $s[1,7]$ 虽然存在一个前缀 $\texttt{abca}$ 和它的等长后缀相等，但是它们重叠了。因此只有前缀 $\texttt{a}$ 满足条件。

给定 $s$，求 $(\sum \limits_{i=1}^{n} (\operatorname{num}_i+1)) \bmod 10^9+7$。

题解

$\operatorname{num}$ 和前文 $\operatorname{maxlen}$ 唯一的区别是，前者不允许前后缀重叠而后者可以。

算法一

首先记录下，每个 $s[1,i]$ 在不考虑重叠的情况下，有多少个前缀和自己的等长后缀相等，记作 $\operatorname{cnt}_i$。$\operatorname{cnt}_i$ 满足 $\operatorname{cnt}_i = \operatorname{cnt}_{\operatorname{maxlen_i}}+1$。

对于每个 $i$，设置指针 $j = \operatorname{maxlen}_i$。如果 $j \geq \left \lfloor \dfrac i2 \right \rfloor$，此时发生了重叠，那么将 $j$ 改为 $ \operatorname{maxlen}_i+1$（类似于 KMP 跳前缀的过程），否则 $\operatorname{num}_i$ 就是 $\operatorname{cnt}_j$。

因为 $j$ 每次最少减少 $1$，所以复杂度为 $O(n^2)$。
算法二

考虑优化算法一。我们发现在处理下一个 $i$ 时，之前得到的 $j$ 可以沿用。如果 $s_{i+1} = s_{j}$，$j$ 增加 $1$，否则 $j$ 不断跳前缀直到 $s[1,j] = s[1,(i+1)-j+1]$ 或 $j=0$。

$j$ 最多增加 $n$ 次，从而最多减少 $n$ 次，复杂度 $O(n)$。

实现时代码需要在下标范围从 $0$ 开始的版本上略作修改。

# include <bits/stdc++.h>

typedef long long ll;
const int N=1000010,INF=0x3f3f3f3f;
const ll MOD=1e9+7;
ll ans=1;
int n;
int maxlen[N],cnt[N];
char s[N];

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f; 
}
inline void getnext(void){
	int i=2,j=1;
	cnt[1]=1;
	while(i<=n){
		if(s[i]==s[j]){
			maxlen[i]=j,cnt[i]=cnt[j]+1,++i,++j;
		}else if(j==1){
			maxlen[i]=0,cnt[i]=1,++i;
		}else{
			j=maxlen[j-1]+1;
		}
	}
	return;
}
inline void solve(void){
	for(int i=2,j=1;i<=n;++i,++j){
		while(j>1&&s[i]!=s[j])
			j=maxlen[j-1]+1;
		if(j==1&&s[i]!=s[j]){ // j=1 时仍然失配，那么它没用了
			--j; // 如果没有 --j 这一句，for 里面的 ++j 会将它变成 2，导致 WA
			continue;
		}
		while(j>i/2) // 跳前缀
			j=maxlen[j];
		ans=ans*(cnt[j]+1)%MOD;
	}
	return;
}
int main(void){
	int T=read();
	while(T--){
		scanf("%s",s+1),n=strlen(s+1);
		ans=1,getnext(),solve();
		printf("%lld\n",ans);
	} 
	return 0;
}