回文自动机

回文自动机Palindromic Automaton(又称回文树Palindromic Tree,简称pam)能干什么?

对于字符串S[1..n],比如它可以求出S的所有本质不同的回文子串,并求出每一个本质不同的子串在S中出现的次数,当然还能干别的很多事情。

现在来看回文自动机是如何构建的。

定义变量:

cnt表示pam中的节点数,pam的每一个节点分别表示一个本质不同的回文串子串

trans[u][c]表示在节点u所对应的回文子串两边加入字符c时变成的回文串对应的节点(可能不存在)

len[u]表示节点u表示的回文子串的长度

fail[u]表示结尾与u表示的回文子串相同,长度小于len[u]的最长的回文子串所对应的节点(类似AC自动机和KMP的失配指针)

n表示当前字符串的长度(和sam类似,pam也是增量构造的)

s[1..n]表示当前的字符串

last表示结尾是n,长度最长的回文子串对应的节点

num[u]表示u节点表示的回文子串在s[1..n]中出现的次数(这个在增量构造中是不能直接计算的,如果一定要算需要数据结构,因为num[fail[u]]要加在num[u]上,但可以在最后一次性算)

初始化:

一开始pam上有两个节点,0号点和1号点,分别是长度为偶数的回文串的根和长度为奇数的回文串的根。0号点的长度为0,1号点的长度为-1,因为最短的偶数长度的回文串长度是2,奇数的是1,所以减2后是0和-1,感性理解一下。

在最后加入一个字符:

假设当前加入的字符串为s[1..n-1],现在加入字符s[n]。首先找到一个结点u,其对应的字符串要满足结尾为n-1,s[n]==s[n-len[u]-1],长度最大。这个节点只要沿着fail指针向上枚举就可以了,类似KMP。然后如果trans[u][s[n]]存在,则last就等于那个节点,否则如果trans[u][s[n]]不存在,则说明找到了一个与已经找到的回文子串本质不同的回文子串,所以要新建节点v,trans[u][c]就要指向v,len[v]就等于len[u]+2,fail[v]根据定义,应该为trans[w][c],w对应的字符串要满足结尾为n-1,s[n]==s[n-len[w]-1],len[w]<len[u]且len[w]尽可能大。这个求的过程与求u的过程类似。

复杂度

时间复杂度是O(n lg$\sum$),空间复杂度是O(n $\sum$)

模板

BZOJ3676

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
char ch[300005];
int n;
long long ans;
struct Palindromic_Automaton{
    int cnt,trans[300005][26],fail[300005],last,len[300005],num[300005],n,s[300005];
    void init(){
        cnt=2;
        fail[0]=fail[1]=1;
        len[1]=-1;
        s[0]=-1;
    }
    void extand(int c,int n){
        int u=last;
        while(ch[n]!=ch[n-len[u]-1])
            u=fail[u];
        if(!trans[u][c]){
            int v=cnt++;
            len[v]=len[u]+2;    
            int w=fail[u];
            while(ch[n]!=ch[n-len[w]-1])
                w=fail[w];
            fail[v]=trans[w][c];
            trans[u][c]=v;
        }
        last=trans[u][c];
        num[last]++;
    }
    void calc(){
        for(int i=cnt;i>=1;i--){
            num[fail[i]]+=num[i];
            ans=max(ans,(long long)num[i]*len[i]);
        }
    }
}pam;
int main(){
    pam.init();
    scanf("%s",ch+1);
    n=strlen(ch+1);
    for(int i=1;i<=n;i++)
        pam.extand(ch[i]-'a',i);
    pam.calc();
    printf("%lld\n",ans);
    return 0;
}

2 thoughts on “回文自动机”

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注