# 扩展 KMP

解决的问题: 求解母串以 i 位置开始的后缀子串与模式串的最大公共前缀

时复: O (母串长度 + 模式串长度)

引入两个概念,extend [] 数组表示以母串 i 位置开始的后缀子串与模式串的最大公共前缀,next [] 数组表示模式串以 i 位置开始的后缀子串与模式串的最大公共前缀,一个是模式串与母串,一个是模式串与模式串

与 KMP 类似,都采用了利用之前已经得到的信息来优化当前的时间

# 大致过程

记一个 po 表示起始位置,求解 extend 数组需要先求出 next 数组,而求解 next 数组的过程和求 extend 过程一致,只不过是把模式串当作母串

img

(1) 第一步,我们先对原串 S1 和模式串 S2 进行逐一匹配,直到发生不配对的情况。我们可以看到,S1 [0]=S2 [0],S1 [1]=S2 [1],S1 [2]=S2 [2],S1 [3] ≠S2 [3], 此时匹配失败,第一步结束,我们得到 S1 [0,2]=S2 [0,2], 即 extend [0]=3;

(2) Extend [0] 的计算如第一步所示,那么 extend [1] 的计算是否也要从原串 S1 的 1 位置,模式串的 0 位置开始进行逐一匹配呢?扩展 KMP 优化的便是这个过程。从 extend [0]=3 的结果中,我们可以知道,S1 [0,2]=S2 [0,2], 那么 S1 [1.2]=S2 [1,2]。因为 next [1]=4, 所以 S2 [1,4]=S2 [0,3], 即 S2 [1,2]=S [0,1], 可以得出 S1 [1,2]=S2 [1,2]=S2 [0,1], 然后我们继续匹配,S1 [3] ≠S2 [3], 匹配失败,extend [1]=2;

(3) 因为 extend [1]=2, 则 S1 [1,2]=S2 [0,1], 所以 S1 [2,2]=S2 [0,0], 因为 next [0]=5, 所以 S1 [0,5]=S2 [0,5], 所以 S2 [0,0]=S2 [0,0], 又回到 S1 [2,2]=S2 [0,0], 继续匹配下一位,因为 S1 [3] ≠S2 [1], 所以下一位匹配失败,extend [2]=1;

(4) 到计算原串 S1 的 3 号位置(在之前的步骤中能匹配到的最远的位置 + 1, 即发生匹配失败的位置),这种情况下,我们会回到步骤(1)的方式,从原串 S1 的 3 号位置开始和模式串的 0 号位置开始,进行逐一匹配,直到匹配失败,此时的 extend [] 值即为它的匹配长度。因为 S1 [3] ≠S2 [0], 匹配失败,匹配长度为 0,即 extend [3]=0;

(5) 计算 S1 的 4 号位置 extend []。由于原串 S1 的 4 号位置也是未匹配过的,我们也是回到步骤(1)的方式,从原串 S1 的 4 号位置开始和模式串 S2 的 0 号位置开始进行逐一匹配,可以看到,S1 [4]=S2 [0],S1 [5]=S2 [1],S1 [6]=S2 [2],S1 [7]=S2 [3],S1 [8]=S2 [4],S1 [9] ≠S2 [5], 此时原串 S1 的 9 号位置发生匹配失败,最多能匹配到原串 S1 的 8 号位置,即 S1 [4,8]=S2 [0,4], 匹配长度为 5,即 extend [4]=5;

(6) 计算 S1 的 5 号位置 extend []. 由于原串 S1 的 5 号位置是匹配过的(在步骤(5)中匹配了),我们从 extend [4]=5 得出,S1 [4,8]=S2 [0,4], 即 S1 [5,8]=S2 [1,4], 和步骤(2)的计算方式类似,我们从 next [1]=4 可知,S2 [0,3]=S2 [1,4], 即 S1 [5,8]=S2 [0,3], 然后我们继续匹配原串 S1 的 9 号位置和 S2 的 4 号位置,S1 [9]=S2 [4], 继续匹配,S1 [10]=S2 [5], 此时原串 S1 的所有字符皆匹配完毕,皆大欢喜,则 S1 [5,10]=S2 [0,5],extend [5]=6;

(7) 从原串 S1 的 6 号位置到 10 号位置的 extend [] 的计算,与原串 S1 的 1 号位置到 3 号位置的计算基本相同。S1 [6,10]=S2 [1,5], 因为 next [1]=4,所以 S2 [1,4]=S [0,3], 所以 S1 [6,9]=S2 [0,3], 此时不在需要判断匹配下一位的字符了,直接 extend [6]=4;(具体原因在后面的分析总结中有说明)

(8) S1 [7,10]=S2 [2,5], 因为 next [3]=2, 所以 S2 [3,4]=S2 [0,1], 所以 S1 [8,9]=S2 [0,1], 匹配长度为 2,即 extend [7]=3;

(9) S1 [8,10]=S2 [3,5], 因为 next [3]=2, 所以 S2 [3,4]=S2 [0,1], 所以 S1 [8,9]=S2 [0,1], 匹配长度为 2,即 extend [8]=2;

(10) S1 [9,10]=S2 [4,5], 因为 next [4]=1, 所以 S2 [4,5]=S2 [0,0], 所以 S1 [9,9]=S2 [0,0], 匹配长度为 1,即 extend [9]=1;

(11) S1 [10,10]=S2 [5,5], 因为 next [5]=0, 所以匹配长度为 0,即 extend [10]=0;

至此,所有的匹配已经结束,相信,如果你仔细的看了上述的例子,已经对扩展 KMP 有了一定的了解了,它的计算过程中,主要是步骤一和步骤二的计算过程。下面我们对这两个过程归纳一下:

img

我们可以得出,len=next [k+1-Po],S2 [0,len-1]=S2 [k+1-Po,k+Po+len], 所以 S1 [k+1,k+len]=S2 [k+1-Po,k+Po+len]=S2 [0,len-1], 即 extend [k+1]=len;

那么会不会出现 S1 [k+len+1]=S2 [len] 的情况呢?答案是否定的

假如 S1 [k+len+1]=S2 [len], 则 S1 [k+1,k+len+1]=S2 [0,len]

因为 k+len<P, 所以 k+len+1<=P

所以 S1 [k+1,k+len+1]=S2 [k+1-Po,k+Po+len+1]=S2 [0,len]

此时,next [k+1-Po]=len+1 与原假设不符合,所以此时 S1 [k+len+1]≠S2 [len], 不需要再次判断。

(2)当(k+1)+len-1=k+len>=P 时,即以下情况:

img

我们可以看出,由 S1 [Po,P]=S2 [0,P-Po] 可得出 S1 [k+1,P]=S2 [k+1-Po,P-po],len=next [k+1-Po], 所以 S2 [0,len-1]=S2 [k+1-Po,k+len+Po]

所以 S1 [k+1,p]=S2 [0,P-k-1]

由于大于 P 的位置我们还未进行匹配,所以从原串 S1 的 P+1 位置开始和模式串的 P-k 位置开始进行逐一匹配,直到匹配失败,并更新相应的 Po 位置和最远匹配位置 P, 此时 extend [k+1]=P-k + 后来逐一匹配的匹配长度。

其实,next [] 数组的计算过程与 extend [] 的计算过程基本一致,可以看成是原串 S2 和模式串 S2 的扩展 KMP 进行计算,每次计算 extend [k+1] 时,next [i](0<=i<=k) 已经算出来了,算出 extend [k+1] 的时候,意味着 next [k+1]=extend [k+1] 也计算出来了。

时间复杂度分析

通过上面的算法可知,我们原串 S1 的每一个字符串只会进行一次匹配,extend [k+1] 的计算可以通过之前 extend [i](0<=i<=k) 的值得出,由于需要用相同的方法对模式串 S2 进行一次预处理,所以扩展 KMP 的时间复杂度为 O (l1+l2), 其中,l1 为原串 S1 的长度,l2 为模式串 S2 的长度。

# 代码

void getnext(string T){
	int len=T.size();
	nex[0]=len;
	int p=0;
	while(p+1<len && T[p]==T[p+1]) p++;  // 这里注意把边界写在前面
	nex[1]=p;
	int po=1;
	for(int i=2;i<len;i++){
		if(i+nex[i-po]<po+nex[po]) nex[i]=nex[i-po];  // 第一种情况,直接得到答案
		else{
			int j=po+nex[po]-i;  
			if(j<0) j=0;  // 超出已匹配的字符串长度,需要重新匹配
			while(i+j<len && T[i+j]==T[j]) j++;
			nex[i]=j;
			po=i;  // 长度超出,更新起始位置
		}
	}
}
void extmp(string S,string T){
	int len1=S.size(), len2=T.size();
	getnext(T);
	int p=0;
	while(p<len1 && p<len2 && S[p]==T[p]) p++;  // 边界写到前面
	ext[0]=p;
	int po=0;
	for(int i=1;i<len1;i++){
		if(i+nex[i-po]<po+ext[po]) ext[i]=nex[i-po];
		else{
			int j=po+ext[po]-i;
			if(j<0) j=0;
			while(i+j<len1 && j<len2 && T[j]==S[i+j]) j++;
			ext[i]=j;
			po=i;
		}
	}
}

# 武辰延的字符串

题目

image-20210407203042725

可以用扩展 KMP 来做,将 s2 当作母串,对于 s1 和 s1 的公共前缀子串,每一个位置的 extend 值累加起来就是答案

# code

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
string S,T;
long long ext[110000],nex[110000];
void getnext(string T){
	int len=T.size();
	nex[0]=len;
	int p=0;
	while(p+1<len && T[p]==T[p+1]) p++;
	nex[1]=p;
	int po=1;
	for(int i=2;i<len;i++){
		if(i+nex[i-po]<po+nex[po]) nex[i]=nex[i-po];
		else{
			int j=po+nex[po]-i;
			if(j<0) j=0;
			while(i+j<len && T[i+j]==T[j]) j++;
			nex[i]=j;
			po=i;
		}
	}
}
void extmp(string S,string T){
	int len1=S.size(), len2=T.size();
	getnext(T);
	int p=0;
	while(p<len1 && p<len2 && S[p]==T[p]) p++;
	ext[0]=p;
	int po=0;
	for(int i=1;i<len1;i++){
		if(i+nex[i-po]<po+ext[po]) ext[i]=nex[i-po];
		else{
			int j=po+ext[po]-i;
			if(j<0) j=0;
			while(i+j<len1 && j<len2 && T[j]==S[i+j]) j++;
			ext[i]=j;
			po=i;
		}
	}
}
int main()
{
	ios;
	cin>>T>>S;
	extmp(S,T);
	long long len1=T.size(),len2=S.size(),ans=0;
	for(int i=0;i<len1;i++){
		if(i>=len2) break;
		if(T[i]!=S[i]) break;
		ans+=ext[i+1];
	}
	cout<<ans<<'\n';
	return 0;
 }
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝