欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

回文自动机

程序员文章站 2022-06-10 22:20:14
...

Palindrome auto machine

又称回文树,顾名思义,对于一个字符串的回文树来说,每个节点表示一个回文串。
例:abbabba
对应节点有:a,b,bb,bab,abba,bbabb
用于统计某字符串有多少个回文子串之类问题。

Q1 节点会不会很多?

考虑每添加一个字符对回文树节点个数的影响
回文自动机
如图所示,当添加c后,考虑以c为结尾最长的回文串A,假设A未在回文树中出现过,那么节点树+1,并且不存在比A短并且未在回文树中出现的情况,所以每加入一个字符最多添加n个节点,所以回文树节点数和字符串数等价。

Q2 怎么建树?

由于回文串分奇回文和偶回文,所以先建立两个根节点0 1
分别表示回文串的根节点和回文串的根节点。
所以转移函数就为

trans[i][c] = j 表示从i节点代表的回文子串两头拼接上相同的字符c, 变成了j节点代表的回文子串.

那么考虑增量转移,即对于第i个字符,怎么确定他是由当前回文树中那个节点转移得到的?
fail指针(和AC自动机类似的构造思想),每个节点fail含义为,该节点代表的最长非自身回文后缀
定义last表示以i-1为结尾的最长回文后缀的节点,那么如果要找以i为后缀的最长回文后缀的节点就相当于不断找满足s[i-pam[last].len-1]==s[i]的过程,即

while(s[i-pam[u].len-1]^s[i]) u=pam[u].fail;

所以trans[u][s[i]] 就是我们要找的以i为后缀的最长回文后缀的节点
那么当这个节点没出现过时,我们就把这个节点加入回文树中,并且由于还要为接下来的字符建立fail指针,设z为当前节点,fa为z的父亲节点,那么

int w=getfail(i,pam[fa].fail);
pam[z].fail=pam[w].trans[c];

并且由于最长非自身回文后缀一定在回文树中出现过,所以不需要考虑pam[z].fail==0的情况(至于为什么,前面已经说过了)

这样我们只需不断添加字符,重复上述过程就能构造出一颗回文树了

Q3 建树后可以求什么?

1 求串S前缀1~i中本质不同回文串个数(tot-1)
2 求串S内每一个本质不同回文串出现次数
3 求串S内回文串个数
4 求以下标i结尾的回文串个数

Q4 怎么求?

定义一些变量:
len表示当前节点对应回文子串长度
num表示前pam节点(即读入s[i]之后,s[1,…,i]的最长回文后缀对应节点u)对应回文子串的所有不同回文后缀的个数(包括自身)
sz表示当前节点对应回文子串在主串中出现次数(需要处理完整个主串后倒着对failDP)

具体请看模板????

模板

const int SZ = 26;///字符集
const int maxn = 1e6 + 6;
struct PAM {
    struct PamNode{int fail,trans[SZ],sz,len,num;}pam[maxn];
    int tot;char s[maxn];
    void init() {
        tot=1;
        pam[0].fail=1;pam[0].len=0;
        pam[1].fail=1;pam[1].len=-1;
        memset(pam[0].trans,0,SZ*sizeof (int));
        memset(pam[1].trans,0,SZ*sizeof (int));
    }
    inline int newnode(int len) {
        tot++;
        memset(pam[tot].trans,0,SZ*sizeof (int));
        pam[tot].len=len;pam[tot].fail=0;
        pam[tot].sz=0;pam[tot].num=0;
        return tot;
    }
    inline int getfail(int i,int u) {
        while(s[i-pam[u].len-1]^s[i]) u=pam[u].fail;
        return u;
    }
    inline int append(int i,int u) {
        int c=s[i]-'a';
        int fa=getfail(i,u);
        u=pam[fa].trans[c];
        if(!u) {
            int z=newnode(pam[fa].len+2);
            int w=getfail(i,pam[fa].fail);
            pam[z].fail=pam[w].trans[c];
            u=pam[fa].trans[c]=z;///注意这里要后更新,否则上面getfail时可能导致死循环
            pam[z].num=pam[pam[z].fail].num+1;
/*还有一点我们可以指出, 这里属于z代表的回文子串第一次出现, 之前读入s[1,..,i-1]都是没有出现过该回文子串
的, 所以可以维护出每种回文子串第一次出现的索引.只是这里没做而已.
*/
        }
        pam[u].sz++;return u;
    }
    void calu() {
        for(int i=tot,fail;i>1;i--) {
            fail=pam[i].fail;
            pam[fail].sz+=pam[i].sz;
        }
    }
}pa;

例题:

P5496

相关标签: 算法学习