扩展kmp——神奇的字符串匹配

## 一、引言 一个算是冷门的算法（在竞赛上），不过其算法思想值得深究。 ## 二、前置知识 1. kmp的算法**思想**，具体可以参考[这篇日报](https://pks-loving.blog.luogu.org/zi-fu-chuan-xue-xi-bi-ji-qian-xi-kmp-xuan-xue-di-dan-mu-shi-chuan-pi-post)。 1. **trie树（字典树）**。 ## 三、经典扩展kmp模板问题： 扩展kmp的模板问题： >给你两个字符串s,t，长度分别为n,m。 >请输出s的每一个后缀与t的最长公共前缀。 ~~哈希是不可能的，这辈子都不可能的。~~ $\mathcal{AC}$自动机？好像更不可做了。 我们先定义一个：$extend[i]$表示$S[i...n]$与$T$的最长公共前缀长度，而题意就是让你求所有的$extend[i]$。 ##### 注：以下字符串均从1开始计位。 ## 例子： 如果$S=aaaaaaaaaabaa$，$n=13$ $T=aaaaaaaaaaa$，$m=11$  由图可知，$extend[1]=10$、$extend[2]=9$。 我们会发现：在求$extend[2]$时，我们耗费了很多时间，但我们可以利用$extend[1]$来更快速地求解： 因为已经计算出$extend[1]=10$。 所以有：$S[1...10]=T[1...10]$ 然后得：$S[2...10]=T[2...10]$ 因为计算$extend[2]$时，实际上是$S[2...n]$和$T$的匹配， 又因为刚刚求出了$S[2...10]=T[2...10]$， 所以匹配的**开头阶段**是求$T[2...10]$与$T$的匹配。 这时我们可以设置辅助参数：$next$，$next[i]$表示$T[i,m]$与$T$的最长公共前缀长度。 那么对于上述的例子：$next[2]=10$ 即：$T[2...11]=T[1...10]$ 然后得：$T[2...10]=T[1...9]$ $∴S[2...10]=T[2...10]=T[1...9]$ **也就是说求$extend[2]$的匹配的前9位已经匹配成功了，不用再匹配一遍了，可以直接从$S[11]$和$T[10]$开始匹配，这样我们就省下了很多时间。** 这其实就是kmp的思想。 ## 对于一般情况： 设$extend[1...k]$已经算好，并且在以前的匹配过程中在S串中的最远位置是$p$，即$p=max(i+extend[i]-1)$，其中$i=1...k$。 然后我们设取这个最大值k的位置是$p0$。  **首先，根据定义，$S[p0...p]=T[1...p-p0+1]$。** 我们设$T[k-p0+1]$在$T$串中对应的位置为$a$，$T[k-p0+2]$在$T$串中所对应的位置为$b$。~~（仅仅是为了下面的讲解方便）~~ 然后令$L=next[b]$。 下面分两种情况讨论： ## 第一种情况：$k+L<p$ 也就是$S[k+L]$这个位置在$p$前面，如图：  我们设$l1=1$，$r1=L$，$l2=b$，$r2=b+L-1$。（$b$的定义在上一张图） 此时$l1$、$r1$、$l2$、$r2$的位置如图所示。 也就是说，$T[l1...r1]=T[l2...r2]$。 **即$\color{red}{\text{红线}}$与$\color{green}{\text{绿线}}$与$\color{blue}{\text{蓝线}}$相等。** 然后由$next$的定义可知，$T[r1+1]!=T[r2+1]$。 又因为$T[r2+1]=S[k+L+1]$ 所以$T[r1+1]!=S[k+L+1]$，这两个字符不一样。 **又因为$\color{red}{\text{红线}}$与$\color{blue}{\text{蓝线}}$相等，这两条线已经匹配成功。** **所以$extend[k+1]=L$，也就是$next[b]$。** 所以这段的代码比较简单： ```cpp if(i+nxt[i-p0]<extend[p0]+p0)extend[i]=nxt[i-p0]; //i相当于k+1 //nxt[i-p0]相当于L //extend[p0]+p0相当于p //因为在代码里我是从0开始记字符串的，所以本应在小于号左侧减1，现在不用了。 ``` ## 第二种情况：$k+L>=p$ 也就是$S[k+L]$这个位置在p前面，如图：  ~~图可能略丑~~ 同样，我们设$l1=1$，$r1=L$，$l2=b$，$r2=b+L-1$。 此时$l1$、$r1$、$l2$、$r2$的位置如图所示。（$r1$的位置可能在$p-p0+1$前或后） **同理，$\color{red}{\text{红线}}$与$\color{green}{\text{绿线}}$与$\color{blue}{\text{蓝线}}$相等。** 那么我们设$(k+L)$到$p$的这段距离为$x$。 那么$S[k+1...(k+L)-x+1]=S[k+1...p]$。 又因为： $T[l1...r1-x+1]=T[l2...r2-x+1]=S[k+1...(k+L)-x+1]$ **即$\color{blue}{\text{S1}}\color{black}{=}\color{red}{\text{S2}}\color{black}{=}\color{green}{\text{S3}}$。** 所以$T[l1...r1-x+1]=S[k+1...p]$， 也就是说$T[1...r1-x+1]=S[k+1...p]$，这一段已经匹配成功了。 **即$\color{blue}{\text{S1}}$与$\color{red}{\text{S2}}$是相等的，已经匹配成功了。** **那么我们就可以从$S[p+1]$和$T[r1-x+2]$开始暴力匹配了，无需再考虑前面的东西。** 那么这段的代码长这样： ```cpp int now=extend[p0]+p0-i; now=max(now,0);//这里是防止i>p while(t[now]==s[i+now]&&now<(int)t.size()&&now+i<(int)s.size())now++;//暴力求解的过程 extend[i]=now; p0=i;//更新p0 ``` ## 求$next$ 求$extend$的大部分过程已经完成了，现在就剩怎么求$next$了，我们先摸清一下求$next$的本质： >求T的每一个后缀与T的最长公共前缀长度 听起来好熟悉，我们再看一下题面： >求S的每一个后缀与T的最长公共前缀长度 **我们发现求$next$的本质和求$extend$的本质是一样的，所以我们~~直接复制~~重新打一遍就好了。** **这其实和$kmp$的思想很相似，因为$kmp$也是自己匹配一遍自己，再匹配文本串。** **要注意的一点是：求$next$时我们要从第2位（也就是代码中的第1位）开始暴力，这样能防止求$next$时引用自己$next$值的情况。** ## 时间复杂度 因为求$next$的时间复杂度是$O(m)$，求$extend$的时间复杂度是$O(n)$，所以总时间复杂度：$O(n+m)$，即$S$串与$T$串的长度之和。 ## Code ```cpp #include<bits/stdc++.h> #define N 1000010 using namespace std; int q,nxt[N],extend[N]; string s,t; void getnxt() { nxt[0]=t.size();//nxt[0]一定是T的长度 int now=0; while(t[now]==t[1+now]&&now+1<(int)t.size())now++;//这就是从1开始暴力 nxt[1]=now; int p0=1; for(int i=2;i<(int)t.size();i++) { if(i+nxt[i-p0]<nxt[p0]+p0)nxt[i]=nxt[i-p0];//第一种情况 else {//第二种情况 int now=nxt[p0]+p0-i; now=max(now,0);//这里是为了防止i>p的情况 while(t[now]==t[i+now]&&i+now<(int)t.size())now++;//暴力 nxt[i]=now; p0=i;//更新p0 } } } void exkmp() { getnxt(); int now=0; while(s[now]==t[now]&&now<min((int)s.size(),(int)t.size()))now++;//暴力 extend[0]=now; int p0=0; for(int i=1;i<(int)s.size();i++) { if(i+nxt[i-p0]<extend[p0]+p0)extend[i]=nxt[i-p0];//第一种情况 else {//第二种情况 int now=extend[p0]+p0-i; now=max(now,0);//这里是为了防止i>p的情况 while(t[now]==s[i+now]&&now<(int)t.size()&&now+i<(int)s.size())now++;//暴力 extend[i]=now; p0=i;//更新p0 } } } int main() { cin>>s>>t; exkmp(); int len=t.size(); for(int i=0;i<len;i++)printf("%d ",nxt[i]);//输出nxt puts(""); len=s.size(); for(int i=0;i<len;i++)printf("%d ",extend[i]);//输出extend return 0; } ``` 洛谷上有一道扩展$kmp$的模板题：[P5410【模板】扩展 KMP](https://www.luogu.org/problemnew/show/P5410) $bzoj$和$hdu$上也有几道，大家可以去看看： [hdu2594 Simpsons’ Hidden Talents](http://acm.hdu.edu.cn/showproblem.php?pid=2594) [hdu4333 Revolving Digits](http://acm.hdu.edu.cn/showproblem.php?pid=4333)