专栏文章

笔记 · 一些字符串

aaleph_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miohtfat
此快照首次捕获于
2025/12/02 19:26
3 个月前
此快照最后确认于
2025/12/02 19:26
3 个月前
查看原文

KMP

KMP算法可以在 O(n+m)\mathcal{O}(n+m) 的时间复杂度内完成串的匹配。
其核心思想在于 nxtnxt 数组（也叫 border/failborder/fail）。nxt[i]nxt[i] 的意义是：前缀 [1,i][1,i] 最长相同的真前缀和真后缀的长度。
例如 abcabb，nxt[5]nxt[5] 的值为 22（ab）
那这有什么用呢？考虑匹配长度为 nn 的文本串 ss 和长度为 mm 的模式串 tt。我们先对 tt 求出 nxtnxt。
在失配时，暴力做法是一位一位移动重新尝试，然而KMP算法是这样处理的：枚举文本串的位置 ii。
  • 如果此时考虑到模式串的第 jj 位（ t[1,j]t[1,j] 位是匹配上的），而 s[i]s[i] 与 t[j+1]t[j+1] 失配。这时令 j←nxt[j]j\leftarrow nxt[j]，相当于把模式串向后移动了一段位置，使得前缀覆盖了后缀那段相同的位置，跳过了中间必然不可能匹配的位置，这就是KMP的核心思想。如果接下来 j+1j+1 还是失配，就再重复（注意 j=0j=0 就不能再往前跳了）。
  • 如果 ii 和 jj 成功匹配上了，那么简单的 i++,j++ 即可。
  • 如果 j==m，说明匹配成功。此时我们要想找出所有的匹配，就得先让其失配，j←nxt[j]j\leftarrow nxt[j]。
好了，那现在问题就变成了怎么求出 nxtnxt 数组。我们考虑让模式串自己匹配自己。这也是很多人（包括我）初学kmp最不能理解的一点。
可以想象将模式串复制一份，错位开来。
CPP
abcabc
 abcabc
我们现在要匹配这两个串。用 ii 枚举第一个串，jj 表示第二串匹配到哪了。考虑类似的匹配过程，现在要求 nxt[i]nxt[i]。
  • 如果 ii 和 j+1j+1 失配，我们还能令 j←nxt[j]j\leftarrow nxt[j] 吗？答案是可以的，因为 j≤ij\le i，nxt[j]nxt[j] 已经求出过。这一步是一样的。
  • 如果 ii 和 jj 成功匹配上，简单的 i++,j++ 即可。
  • 以上过程结束后，第二个串的前缀就匹配到了第一个串的后缀，并且是最长的。而这正是 nxtnxt 数组的意义，赋值 nxt[i]=j 即可。
实际操作中，先令 nxt[1]=0，用两个指针在模式串上跑就行了。

Manacher

Manacher算法可以在 O(n)\mathcal{O}(n) 的时间复杂度内求解出以每个位置为中心的最长回文半径 pp。
经典问题：求最长回文子串长度（求最长回文直径，两个是一样的）
先考虑这件事情暴力怎么求。光枚举每个字符作为中心是不行的，因为偶数长度的回文子串的中心在两个字符之间。所以我们先在两两字符之间插入辅助字符，变成一个长度为 2n+12n+1 的字符串，然后从左往右枚举每个字符，向两边扩展，这样做是 O(n2)\mathcal{O}(n^2) 的。
如何优化呢？我们考虑求出了最长回文半径，即可求出最长回文直径了。考虑记录两个值：
RR：对于此前考虑过的所有位置，以它们为回文中心最右能扩展到的位置。
mid\text{mid}：具体是哪个位置，把它作为回文中心后，让右边界成功扩展到了 RR。
设 RR 关于 mid\text{mid} 的对称点为 LL，显然 [L,R][L,R] 是一个大回文串。
假如现在考虑到位置 ii。如果 i>Ri>R，那不好意思，只能暴力扩充了。
如果 i≤Ri\le R 呢？
考虑回文串的性质：关于【回文中心】对称的两个串，实际上是全等的，只不过一个是正序，一个是逆序。那么我们可以尝试借助 ii 关于 mid\text{mid} 的对称点 i′=2mid−ii'=2\text{mid}-i，借助 pi′p_{i'} 确定 pip_i 的下限，在此基础上进行扩展。
  • 如果 i′i' 的回文区域全部在 (L,R](L,R] 内，那么 ii 的回文区域就和 i′i' 的完全一致了，自然有 pi=pi′p_i=p_{i'}。
  • 如果 i′i' 的回文区域左端到达甚至超出了 LL，因为 ii 右边的区域暂时还不明朗，所以我们只能说，ii 的回文区域的右边界也一定不小于 RR，即 pi≥r−i+1p_i\ge r-i+1，这时就需要暴力扩充了。
以上步骤可以形式化如下：
  • 对于每个 ii，如果它不在右边界范围内，直接进入下一步；否则就可以先给出一个下限 pi=min⁡{p2mid−i,r−i+1}p_i=\min\{p_{2\text{mid}-i},r-i+1\}。
  • 然后在下限的基础上尝试向两边暴力扩充。这里有个细节，那就是提前让 00 号位置为一个和所有字符都不一样的字符，这样扩充到了 00 就一定会停止了。
  • 现在确定了 pip_i，再将新的右边界 R′=pi+i−1R'=p_i+i-1 和 RR 进行比较，尝试更新 RR 与 mid\text{mid}。
时间复杂度证明：右边界 RR 一定是单调递增的，最多往右移动 O(n)\mathcal{O}(n) 次。

P3805 Manacher模版题

求解过程不再赘述，和上述一致。
注意一下答案的更新。现在求出的回文半径 pp 是带有特殊字符的。可以证明 pp 一定为偶数，且每 pp 个字符有一半是特殊字符，实际上的回文半径为 p2\frac{p}{2}，则回文直径为 2×p2−1=p−12\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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...