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

一、引言

一个算是冷门的算法（在竞赛上），不过其算法思想值得深究。

二、前置知识

1. kmp的算法思想，具体可以参考这篇日报。

2. trie树（字典树）。

三、经典扩展kmp模板问题：

扩展kmp的模板问题：

给你两个字符串s,t，长度分别为n,m。

请输出s的每一个后缀与t的最长公共前缀。

哈希是不可能的，这辈子都不可能的。

我们先定义一个：$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]。

所以这段的代码比较简单：

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]开始暴力匹配了，无需再考虑前面的东西。

那么这段的代码长这样：

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

#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

[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)