题解 P5410 【【模板】扩展 KMP】

ez_lcw · 2019-05-20 13:51:22 · 题解

一、引言

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

二、前置知识

kmp 的算法思想，具体可以参考这篇日报。
trie 树（字典树）。

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

扩展 kmp 的模板问题：

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

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

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

AC 自动机？好像更不可做了。

我们先定义一个：extend[i] 表示 S[i...n] 与 T 的最长公共前缀长度，而题意就是让你求所有的 extend[i]。

注：以下字符串均从1开始计位。

例子：

如果 S=\texttt{aaaaaaaaaabaa}，n=13，

![](https://cdn.luogu.com.cn/upload/pic/54062.png) 由图可知，$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$。然后我们设取到这个最大值 $p$的位置是 $p0$。 ![](https://cdn.luogu.com.cn/upload/pic/54070.png) **首先，根据定义，$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 的位置如图所示。

由 next 的定义，也就是说，T[l1...r1]=T[l2...r2]。

注：以下所写的“线”相等指的是长度和字符都相等

即 \color{red}{\text{红线}} 与 \color{green}{\text{绿线}} 与 \color{blue}{\text{蓝线}} 相等。

然后由 next 的定义可知，T[r1+1]\neq T[r2+1]。

又因为 T[r2+1]=S[k+L+1]，

所以 T[r1+1]\not =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，现在不用了。

第二种情况：p\leqslant k+L

也就是 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 20000010 

using namespace std;

int q,nxt[N],extend[N];
int slen,tlen;
char s[N],t[N];

void getnxt()
{
    nxt[0]=tlen;//nxt[0]一定是T的长度
    int now=0;
    while(t[now]==t[1+now]&&now+1<tlen)now++;//这就是从1开始暴力
    nxt[1]=now;
    int p0=1;
    for(register int i=2;i<tlen;i++)
    {
        if(i+nxt[i-p0]<nxt[p0]+p0)nxt[i]=nxt[i-p0];//第一种情况
        else
        {//第二种情况
            now=nxt[p0]+p0-i;
            now=max(now,0);//这里是为了防止i>p的情况
            while(t[now]==t[i+now]&&i+now<tlen)now++;//暴力
            nxt[i]=now;
            p0=i;//更新p0
        }
    }
}

void exkmp()
{
    getnxt();
    int now=0;
    while(s[now]==t[now]&&now<min(slen,tlen))now++;//暴力
    extend[0]=now;
    int p0=0;
    for(register int i=1;i<slen;i++)
    {
        if(i+nxt[i-p0]<extend[p0]+p0)extend[i]=nxt[i-p0];//第一种情况
        else
        {//第二种情况
            now=extend[p0]+p0-i;
            now=max(now,0);//这里是为了防止i>p的情况
            while(t[now]==s[i+now]&&now<tlen&&now+i<slen)now++;//暴力
            extend[i]=now;
            p0=i;//更新p0
        }
    }
}

int main()
{
    scanf("%s%s",s,t);
    slen=strlen(s),tlen=strlen(t);
    exkmp();
    long long z=0,p=0;
    for(register int i=0;i<tlen;i++)z^=1ll*(i+1)*(nxt[i]+1);//输出nxt
    for(register int i=0;i<slen;i++)p^=1ll*(i+1)*(extend[i]+1);//输出extend
    printf("%lld\n%lld\n",z,p);
    return 0;
}