笔记 · 一些字符串
aleph_
·
·
个人记录
KMP
KMP算法可以在 \mathcal{O}(n+m) 的时间复杂度内完成串的匹配。
其核心思想在于 nxt 数组（也叫 border/fail）。nxt[i] 的意义是：前缀 [1,i] 最长相同的真前缀和真后缀的长度。
例如 abcabb，nxt[5] 的值为 2（ab）
那这有什么用呢？考虑匹配长度为 n 的文本串 s 和长度为 m 的模式串 t。我们先对 t 求出 nxt。
在失配时，暴力做法是一位一位移动重新尝试，然而KMP算法是这样处理的：枚举文本串的位置 i。
- 如果此时考虑到模式串的第 j 位（ t[1,j] 位是匹配上的），而 s[i] 与 t[j+1] 失配。这时令 j\leftarrow nxt[j]，相当于把模式串向后移动了一段位置，使得前缀覆盖了后缀那段相同的位置，跳过了中间必然不可能匹配的位置，这就是KMP的核心思想。如果接下来 j+1 还是失配，就再重复（注意 j=0 就不能再往前跳了）。
- 如果 i 和 j 成功匹配上了，那么简单的
i++,j++ 即可。
- 如果
j==m，说明匹配成功。此时我们要想找出所有的匹配，就得先让其失配，j\leftarrow nxt[j]。
好了，那现在问题就变成了怎么求出 nxt 数组。我们考虑让模式串自己匹配自己。这也是很多人（包括我）初学kmp最不能理解的一点。
可以想象将模式串复制一份，错位开来。
abcabc
abcabc
我们现在要匹配这两个串。用 i 枚举第一个串，j 表示第二串匹配到哪了。考虑类似的匹配过程，现在要求 nxt[i]。
- 如果 i 和 j+1 失配，我们还能令 j\leftarrow nxt[j] 吗？答案是可以的，因为 j\le i，nxt[j] 已经求出过。这一步是一样的。
- 如果 i 和 j 成功匹配上，简单的
i++,j++ 即可。
- 以上过程结束后，第二个串的前缀就匹配到了第一个串的后缀，并且是最长的。而这正是 nxt 数组的意义，赋值
nxt[i]=j 即可。
实际操作中，先令 nxt[1]=0，用两个指针在模式串上跑就行了。
Manacher
Manacher算法可以在 \mathcal{O}(n) 的时间复杂度内求解出以每个位置为中心的最长回文半径 p。
经典问题：求最长回文子串长度（求最长回文直径，两个是一样的）
先考虑这件事情暴力怎么求。光枚举每个字符作为中心是不行的，因为偶数长度的回文子串的中心在两个字符之间。所以我们先在两两字符之间插入辅助字符，变成一个长度为 2n+1 的字符串，然后从左往右枚举每个字符，向两边扩展，这样做是 \mathcal{O}(n^2) 的。
如何优化呢？我们考虑求出了最长回文半径，即可求出最长回文直径了。考虑记录两个值：
$\text{mid}$：具体是哪个位置，把它作为回文中心后，让右边界成功扩展到了 $R$。
设 $R$ 关于 $\text{mid}$ 的对称点为 $L$，显然 $[L,R]$ 是一个大回文串。
假如现在考虑到位置 $i$。如果 $i>R$，那不好意思，只能暴力扩充了。
如果 $i\le R$ 呢？
考虑回文串的性质：关于【回文中心】对称的两个串，实际上是全等的，只不过一个是正序，一个是逆序。那么我们可以尝试借助 $i$ 关于 $\text{mid}$ 的对称点 $i'=2\text{mid}-i$，借助 $p_{i'}$ 确定 $p_i$ 的下限，在此基础上进行扩展。
- 如果 $i'$ 的回文区域全部在 $(L,R]$ 内，那么 $i$ 的回文区域就和 $i'$ 的完全一致了，自然有 $p_i=p_{i'}$。
- 如果 $i'$ 的回文区域左端到达甚至超出了 $L$，因为 $i$ 右边的区域暂时还不明朗，所以我们只能说，$i$ 的回文区域的右边界也一定不小于 $R$，即 $p_i\ge r-i+1$，这时就需要暴力扩充了。
以上步骤可以形式化如下：
- 对于每个 $i$，如果它不在右边界范围内，直接进入下一步；否则就可以先给出一个下限 $p_i=\min\{p_{2\text{mid}-i},r-i+1\}$。
- 然后在下限的基础上尝试向两边暴力扩充。这里有个细节，那就是提前让 $0$ 号位置为一个和所有字符都不一样的字符，这样扩充到了 $0$ 就一定会停止了。
- 现在确定了 $p_i$，再将新的右边界 $R'=p_i+i-1$ 和 $R$ 进行比较，尝试更新 $R$ 与 $\text{mid}$。
时间复杂度证明：右边界 $R$ 一定是单调递增的，最多往右移动 $\mathcal{O}(n)$ 次。
### [P3805 Manacher模版题](https://www.luogu.com.cn/problem/P3805)
求解过程不再赘述，和上述一致。
注意一下答案的更新。现在求出的回文半径 $p$ 是带有特殊字符的。可以证明 $p$ 一定为偶数，且每 $p$ 个字符有一半是特殊字符，实际上的回文半径为 $\frac{p}{2}$，则回文直径为 $2\times\frac{p}{2}-1=p-1$。
#### Code
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=110000005;
char s[N<<1];
int n,p[N<<1],ans=0;
void read(){
char c=getchar();
s[0]='~',s[n=1]='|';
while(c<'a'||c>'z') c=getchar();
while(c>='a'&&c<='z'){
s[++n]=c;
s[++n]='|';
c=getchar();
}
}
int main(){
read();
for(int i=1,r=0,mid=0;i<=n;i++){
if(i<=r) p[i]=min(p[(mid<<1)-i],r-i+1);
while(s[i-p[i]]==s[i+p[i]]) ++p[i];
if(p[i]+i>r){
r=p[i]+i-1;
mid=i;
}
ans=max(ans,p[i]-1);
}
cout<<ans<<endl;
}
```