字符串（KMP系列）
sLMxf
·
·
算法·理论
一. KMP
1. border
如果一个字符串的前缀等于他的后缀，我们称这个字符串是原字符串的border。
例如，abcakmeabc 中，abc 就是一个border。
2. KMP
定义一个字符串的 nxt 数组表示：前 i 个字符的最长border长度。
那怎么求一个字符的nxt呢？代码如下：
void kmp(int n,string b)
{
int j=0;
for(int i=2;i<=n;i++)
{
while(j&&b[i]!=b[j+1]) j=nxt[j];
if(b[j+1]==b[i]) j++;
nxt[i]=j;
}
}
时间复杂度 O(n)。
KMP经常用来求解模式串匹配的问题。即询问 s 在 t 中出现的次数。一般来说，代码如下：
j=0;
for(int i=1;i<=m;i++)
{
while(j>0&&b[j+1]!=a[i])
j=nxt[j];
if(b[j+1]==a[i])
j++;
if(j==n)
{
cout<<i-n+1<<endl;
j=nxt[j];
}
}
其中，m=|t|,n=|s|。
原因自己上题解搜。
二. exKMP/扩展KMP/Z函数
1. 什么是 Z 函数
注：字符串从 0 开始编号。
什么是 \text Z 函数呢？我们定义 z_i 表示 s 与 s 的每一个后缀 i\sim n-1 的最长公共前缀（LCP）的长度，此时我们称 z 为 s 的 \text Z 函数。特殊的，\mathbf{z[0]=0}。
举几个栗子：
### 2. Z 函数线性求法
就像 $nxt$ 一样，Z 函数也可以在 $O(n)$ 复杂度中求。
首先假设已知 $z_0,z_1,\cdots,z_{i-1}$，现在要求 $z_i$。
如果 $z_i$ 被求出来了，那么 $s[i,i+z_i-1]$ 一定是 $s$ 的前缀，且 $s[i,i+z_i]$ 一定**不**是 $s$ 的前缀。那么现在正在处理 $z_i$，区间 $s[i,i+z_i-1]$ 就称为我们的**匹配段**，简称 Z-box。
由于 $\LaTeX$ 太难敲了，所以我们简称 $[l,r]$ 是我们的匹配段。由于左端点已知，我们只需要扩展右端点。根据定义，$[l,r]$ 是 $s$ 的前缀。我们维护的时候 $l\le i$，初始 $l=r=0$。
分两种情况讨论
- 当前处理的 $i$ 在 $r$ 的左边（$i\le r$）：由于是匹配段，那么同一长度的 $s$ 肯定是相等的！（因为他们都是 $s$ 的前缀，长度又相等，必然相同）就有性质：$s[i,r]=s[i-l,r-l]$。所以 $z_i=z_{i-l}$？别忘了，$z[i]$ 的长度一定不超过 $r-i+1$（隔着超过字符串长度了？）所以 $z_i\ge\min\{z_{i-l},r-i+1\}$。
- 如果 $z_{i-l}<r-i+1$，那么 $z_i=z_{i-l}$。
- 如果 $z_{i-1}\ge r-i+1$，那么 $z_i=r-i+1$ 的基础上，暴力扩展 $z_i$。
- 如果 $i>r$，暴力扩展
最后，如果 $i+z_i-1>r$，则令 $l=i,r=i+z_i-1$ 即可。
### 3. 代码
```cpp
for(int i=1;i<n;i++)
{
int len=r-i+1;
if(i<=r&&z[i-l]<len) z[i]=z[i-l];
else
{
z[i]=max(0ll,len);
while(i+z[i]<n&&a[z[i]]==b[i+z[i]]) z[i]++;
}
if(i+z[i]-1>r) l=i,r=i+z[i]-1;
}
```
### 4. 时空复杂度分析
容易发现，内层 $r$ 每次至少加一，外层 $i$ 每层加一。总的时间复杂度 $O(n)$。