回文自动机----PAM

定义

1.节点:节点数至多N(字符串长度)个,每个节点表示一个回文串,用s[u]表示,len[u]表示第u个节点表示的回文串的长度.
2.后继边:每个后继边上有一个字母,用trans(u,ch)->v表示u有后继边ch指向v.则有s[v]=ch s[u] ch以及len[v]=len[u]+2.
3.适配边:用fail[u]=v表示u节点的适配边指向了v,则有s[v]是s[u]的最大border,即最长回文后缀.

PAM的构造

PAM在构造时,实际上就是在找每个前缀的最长回文后缀.方法:枚举前一个位置的fail链.
由于回文串有长度为奇数和长度为偶数两种类型,所有我们需要两个根节点–奇根和偶根.
解释:因为我们每次加一个节点,新的节点的长度是旧节点的长度+2,因此需要两个根节点.
并且让fail[0]=1,fail[1]=0,即让奇根和偶根互相指.
我们还需要一个last指针表示我们最后一个访问的点是谁,最初让他指向0号点,即偶根.
插入一个字符ch[i]时,枚举前一个位置的回文后缀,即last的fail链,如果当前枚举到的回文子串p在原串中的两边的字符是我们要插入的字符,即ch[i]==ch[i-len[p]-1]时,以ch[i]结尾的最长回文后缀v就应该放在p节点后面.接着,我们还需要求出v的失配边,也是跳fail链,只不过是从fail[p]开始跳,过程和上面完全相同.

代码

int get_fail(int x) //x表示从哪个节点开始跳
{
    while(s[tot]!=s[tot-len[x]-1])x=fail[x];
    return x;
}
void insert(char c){
    tot++;
    int now=get_fail(last);
    if(!tr[now][c-'a'])
    {
        int x=node(len[now]+2);//新建一个节点，长度是len[now]+2
        fail[x]=tr[get_fail(fail[now])][c-'a'];
        tr[now][c-'a']=x;
    }
    last=tr[now][c-'a'];
    cnt[last]++;
}

例题

1.洛谷 P5496. 【模板】回文自动机 https://www.acwing.com/solution/content/98772/
2.回文串 https://www.acwing.com/solution/content/98775/
3.快乐的jyy https://www.acwing.com/solution/content/98673/
4.双倍回文 https://www.acwing.com/solution/content/98836/
5.最长双回文串 https://www.acwing.com/solution/content/98860/