首页 📚学习笔记

Manacher

是一个求一个字符串中最长回文连续子序列的算法

例如$abaabaabb$最长的就是7

$abaaaaba$最长就是8

$ababbb$最长就是3

注意:一个字符串可能不只有一个最长回文连续子序列

传统做法就是枚举中间点向两边扩展,时间复杂度是$\mathcal O(N^2)$

然后这个算法就优化到了$\mathcal O(N)$(实现质的飞跃)

算法简介

首先回文分为两种:奇回文偶回文

如果枚举的话,有时候是字符,有时候要枚举字符之间的位置,就很麻烦

为了操作方便(因为我们要定义以$i$为中心),我们把它们都变成奇回文

怎么做呢?很简单,全部插入一个符号即可(没出现过)

例如

$abaababa$ ——> $(*a*b*a*a*b*a*b*a*)$

前后是防止越界,你可以随便定义(只要字符串里没有的,不会冲突)

原来$aba$就可以变成$*a*b*a*$

原来$baab$就可以变成$*b*a*a*b*$

这样一来就全部变成了奇回文啦!

我们定义$P[i]$是以$i$为中心的,最长回文串的半径(包括自己)

字符串$($$*$$a$$*$$b$$*$$a$$*$$a$$*$$b$$*$$a$$*$$b$$*$$a$$*$$)$
$P$$1$$1$$2$$1$$4$$1$$2$$7$$2$$1$$4$$1$$2$$1$$4$$1$$2$$1$$1$

我们现在要做的就是$\mathcal O(N)$处理出每一个$P[i]$

考虑能不能根据之前已经得到的来推测出答案呢

当前我们枚举到$i$,已知有一个以$mid$为中心的回文子串,其右端点到了$mx$

可知以$mid$为分界线,左右两边是完全对称的(回文子串定义)

当$i+p[j]<mx$时


我们就可以直接更新答案,因为不可能更长了

当$i+p[j]>=mx$时

我们只能到$mx$这个位置,因为我们不知道$mx$后面是否还能继续匹配

(只取红色部分)
我们就可以根据$i$的对称点$j$来更新答案,但是$p[i]$不一定等于$p[j]$,因为$m$x后面的还是未知的,这一部分暴力匹配就是了

可知$mx$是一直在增大,每增大一次,我们需要比较一次,$mx$最多从$0$到$n$,所以也就是$\mathcal O(N)$的复杂度


其实和$KMP$都有一个运用已知答案的思想

最后输出答案的时候我们半径减一即可(可以自己手%一下找找规律)

P3805 【模板】manacher算法

#include<bits/stdc++.h>
using namespace std;
const int N=11000002;
char s_new[2*N];
char s[N];
int p[2*N];
int INIT(){//转换字符串
    int len=strlen(s);
    s_new[0]='$';
    s_new[1]='#';
    int j=2;
    for(int i=0;i<len;i++){
        s_new[j++]=s[i];
        s_new[j++]='#';
    }
    s_new[j]='\0';
    return j;
}
int manacher(){
    int len=INIT();
    int ans=-1;
    int id;//中心
    int mx=0;//能达到的已知的右端点
    for(int i=1;i<=len;i++){
        if(i<mx)
            p[i]=min(p[2*id-i],mx-i);//更新取较小的一个
        while(s_new[i+p[i]]==s_new[i-p[i]])//暴力扩展
            p[i]++;
        if(mx<i+p[i]){//更新mx
            id=i,
            mx=p[i]+i;
        }
        ans=max(ans,p[i]-1);//更新答案

    }
    return ans;
}
int main(){
    scanf("%s",s);
    cout<<manacher();
    return 0;
}

PAM

$\quad\quad$ 类比AC自动机,我们好像也可以把 $manacher$ 放在自动机上,于是 $PAM$ (回文自动机)就诞生了!

$\quad\quad$ 因为我们有两种回文串(奇回文和偶回文),所以我们的自动机会有两个根节点 $p_0$ 和 $p_1$表示 偶/奇 回文串。从根节点到节点 $p$ 的路径组成的字符串就是一个回文串的半径。然后我们考虑插入

$\quad\quad$ 插入显然可以继承当前最后一个节点的信息。我们把 $s[i]$ 与$s[i-len_{p}-1]$ 比较,如果相同,我们就可以直接继承,否则我们通过跳 $p$ 的 $fail$ 指针来找到以 $s_p$ (当前点代表的字符)为结尾的,最长的回文子串,然后继续比较。

$\quad\quad$ 建立 $fail$ 指针也很简单,插入完后我们只需要继续跳,找到下一个合法节点 $p$ 就是 $fail$ 啦
$\quad\quad$ 考虑最后整理信息,因为 $fail$ 指针肯定是从编号大的指向编号小的,所以我们只需要倒着枚举编号然后把信息传上去即可

初始化

$\quad\quad$ 我们建立$0,1$节点表示 奇偶 回文根节点
$\quad\quad$ $fail[0]=fail[1]=1$
$\quad\quad$ 因为奇回文特殊,所以初始长度设为 $-1$,这样 $+2$ 后就是 $1$
$\quad\quad$ $len[0]=0,len[1]=-1$

【模板】回文自动机(PAM)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
char s[N];
int n;
struct PAM{
    struct point{
        int val,len;
        int son[26],fail;
        point(){
            memset(son,0,sizeof son);
            fail=val=len=0;
        }
    }p[N];
    int idx,last,n;
    PAM(){
        n=-1;
        last=1;
        p[0].len=0;p[1].len=-1;
        p[0].val=0;p[1].val=0;
        p[1].fail=p[0].fail=1;idx=1;
    }
    inline int getfail(int x){
        while(s[n]!=s[n-p[x].len-1])x=p[x].fail;
        return x;
    }
    inline int add(int x){
        ++n;
        int fa=getfail(last);
        if(!p[fa].son[x]){
            ++idx;
            p[idx].fail=p[getfail(p[fa].fail)].son[x];
            p[fa].son[x]=idx;
            p[idx].len=p[fa].len+2;
            p[idx].val=p[p[idx].fail].val+1;
        }
        last=p[fa].son[x];
        return p[last].val;
    }
}P;
signed main(){
    scanf("%s",s);
    n=strlen(s);
    for(int i=0;i<n;i++){
        int ans=P.add(s[i]-'a');
        printf("%d ",ans);
        s[i+1]=(s[i+1]-97+ans)%26+97;
    }
    return 0;
}

$\color{red}{PS:}$先找 $fail$ 指针再确定父子关系,不然 $fail$ 指针会指向自己导致 $TLE$


当然,卡空间的情况下只能用 $Manacher$ ,其余情况 $PAM$ 不更好写??




文章评论

目录