题解 P5410 【【模板】扩展 KMP】
ez_lcw
2019-05-20 13:51:22
## 一、引言
一个算是冷门的算法（在竞赛上），不过其算法思想值得深究。
## 二、前置知识
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$ 的最长公共前缀。
~~哈希是不可能的，这辈子都不可能的。~~
AC 自动机？好像更不可做了。
我们先定义一个：$extend[i]$ 表示 $S[i...n]$ 与 $T$ 的最长公共前缀长度，而题意就是让你求所有的 $extend[i]$。
##### 注：以下字符串均从1开始计位。
## 例子：
如果 $S=\texttt{aaaaaaaaaabaa}$，$n=13$，
$T=\texttt{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$。
然后我们设取到这个最大值 $p$的位置是 $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$ 的位置如图所示。
由 $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]$。**
所以这段的代码比较简单：
```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，现在不用了。
```
## 第二种情况：$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]$ 开始暴力匹配了，无需再考虑前面的东西。**
那么这段的代码长这样：
```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 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;
}
```