Manacher算法和回文自动机(PAM)

super蒟蒻 · 2020-01-20 09:58:00 · 个人记录

这两个东西都是处理关于字符串的回文子串问题的有力工具。

引入

如果让你求你个字符串的最长奇回文子串，怎么求？

我会n^2暴力！枚举对称中心点i，再左右拓展枚举回文半径j。

......
for(int i=0;i<len;i++) {
    int j=1;
    while(i-j>=0 && i+j<len && s[i-j]==s[i+j]) j++;
    ans=max(ans,j*2-1);
}
......

如果字符串长度len很大，这个暴力就不行了。

Manacher算法马拉车

算法流程

其实这个算法也是暴力，只不过是在上面的基础上加了一些优化。

众所周知，暴力之所以超时是因为做了很多重复的计算，那我们考虑一下能不能利用之前算过的答案来进行优化。

假设现在枚举到i，之前有个回文串，它的中心对称点为mid，这个串的右边界为R，是i之前所有回文串最靠右的。

如果i<R:

那么我们可以找到i的对称点i'，假设以i'为中心的回文半径为r(i')。
- 当以i'为中心的回文串并没有扩出去，可以发现r(i)=r(i')。
  
  因为它们都是处在以mid为中心的回文串内，所以上面i'的那个回文串（矩形部分）放到i那里是一样的（因为它们关于mid对称）。
  
  而且i也不能继续扩展了，因为i'最多只能扩到r(i')，再扩展两边就不一样了，那么对称到i这边也同理。
- 当以i'为中心的回文串扩出去了呢？
  
  因为在R右边的字符是未知的，不知道能不能对应到i'那边，所以此时的r(i)=R-i+1。
  
  然后我们就可以暴力扩展了，顺便更新mid=i，右边界R=i+r(i)-1。
如果R<i: 继续暴力扩展及更新。

时间复杂度

可以发现每次要么拓展，要么O(1)得到答案，当R扩展到len时，就不能执行while循环了，所以总的复杂度是O(n)。

一些补充

可是通常题目求的不是奇回文子串，而是奇偶都包括的，偶回文子串怎么求？

在字符之间加一些插板就OK了。

例如：把abababa变成#a#b#a#b#a#b#a#。

可以发现答案就是最大的r(i)-1，画一下样例应该就明白了。

建议可以把再在开头和末尾加上两个不相同的字符，例如：#a#b#c#变成@#a#b#c#&，这样就不用判断边界了。

代码实现

例题：P3805 【模板】manacher算法

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN=11000005;

int n;
char s[MAXN],t[MAXN<<1];

int ans,r[MAXN<<1];
void manacher() { // 开始拉车 
    int mid=1,R=1;
    for(int i=2;i<=n;i++) {
        // 优化 
        if(i<=R) r[i]=min(r[mid*2-i],R-i+1);
        else r[i]=1;
        while(t[i+r[i]]==t[i-r[i]]) r[i]++; // 扩展 
        if(R<i+r[i]-1) mid=i,R=i+r[i]-1; // 更新 
        ans=max(ans,r[i]);
    }
}

int main() {
    scanf("%s",s+1),n=strlen(s+1);
    // 插一些字符 
    for(int i=1;i<=n;i++) t[i<<1]=s[i],t[(i<<1)-1]='#';
    t[n=n<<1|1]='#',t[0]='&',t[n+1]='@';
    manacher();
    printf("%d\n",ans-1);
    return 0;
}

当然也可以写简单点把if去掉

void manacher() {
    int mid=1,R=2;
    for(int i=2;i<=n;i++) {
        r[i]=min(r[mid*2-i],R-i);
        while(t[i+r[i]]==t[i-r[i]]) r[i]++;
        if(R<i+r[i]) mid=i,R=i+r[i];
        ans=max(ans,r[i]);
    }
}

练习题：

P1659 [国家集训队]拉拉队排练
P4555 [国家集训队]最长双回文串
P4287 [SHOI2011]双倍回文

回文自动机(PAM)

未完待续......