String(1):回文树 2019-05-10

PalindromeAutomaton

回文自动机(简称PAM,又称回文树,Palindromic Tree)是一种用于处理回文串的结构。

Palindromic Tree

回文自动机是由两个回文树构成,根结点编号为0,1,分别维护长度为偶数的回文串和长度为奇数的回文串。回文树上的每个节点都代表了一个回文串,每条转移边上有一个字符。
转移边
对于回文树上的节点u,假设u所代表的串为s,如果有一条转移边从(u->v),边上的字符为q,转移到的节点所代表的回文串为q+s+q。
后缀链
对于回文树上的节点u,假设u所代表的串为s,记Str[fail[u]]表示u的后缀链接所链接所代表的回文串,有Str[fail[u]]为s的最长后缀回文串。
记v表示s的一个后缀,fail[s]=v当且仅当不存在v'使得|v'|>|v|且|v'|<|s|且v'为回文串。
节点信息
  • fail[u]:u的后缀链接
  • ch[u][sigma]:u的转移边
  • len[u]:u所代表回文串的长度
  • size[u]:u所代表回文串的出现次数
    特殊地,对于两个根节点,len[1]=-1,len[0]=0,fail[0]=1

    Extend

    类似SAM,当字符集大小为常数的时候插入一个字符的复杂度为O(1)。
    PAM中,我们需要记录上一个插入的点的编号记为lst
  • 插入过程
  • 假设这里插入的字母为'c',现在枚举到第n个位置
    1.从当前lst开始跳fail,直到找到一个位置满足s[n-len[lst]+1]==s[n],也就是在整个串里面满足加入字母'c',可能构成一个回文串。对于边界情况,如果跳到了1号点,s[n-(-1)+1]==s[n]也就是自己和自己一定相等,所以一定会找到一个满足条件的点;如果当前lst不满足,那么找到lst的最长回文后缀进行匹配。
    2.设找到满足条件1的点为p,那么c+p+c为回文串;如果p有一个c的转移边,那么把ch[p][c].size++,否则就需要新开一个点,找到这个新开的点的后缀链接, len[new]=len[p]+2;
    3.如果要新开一个点,那么就要找到他的最长回文后缀,但是这个后缀不能是自己本身,那么考虑从fail[p]开始跳fail,判断条件和刚才相同,找到一个位置满足s[n-len[p]+1]==s[n],这个位置就是fail。


    下图是串'abba'加入字符'a'前后得到的PAM

    Tricks

    本质不同的回文子串数量
    即回文树节点数(不包括根节点)
    每个回文子串的出现次数
    因为一个长串包含短串,所以次数为该子串所对应节点的子树大小
    两个串的相同回文子串对数
    从两个树根开始遍历,如果遍历路径一样则说明对应串一样,然后统计出现次数。

    Code

    BZOJ3676&APIO2014 回文串
    #include <bits/stdc++.h>
    typedef long long LL;
    using namespace std;
    const int maxn = 3e5 + 5;
    const int inf = 0x3f3f3f3f;
    
    char s[maxn], t[maxn];
    
    inline int read() {
        char ch = getchar(); int u = 0, f = 1;
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch))  {u = u * 10 + ch - 48; ch = getchar();} return u * f;
    }
    
    struct PAM {
        int lst, size[maxn], fail[maxn], ch[maxn][26], len[maxn], cnt;
        PAM() {cnt = 1; fail[0] = fail[1] = 1; len[1] = -1;}
        inline void Insert(char c, int n, char *s) {
            int p = lst;
            while(s[n - len[p] - 1] != s[n]) p = fail[p];
            if(!ch[p][c]) {
                int now = ++cnt, k = fail[p];
                len[now] = len[p] + 2;
                while(s[n - len[k] - 1] != s[n]) k = fail[k];
                fail[now] = ch[k][c]; ch[p][c] = now;
            }
            size[ch[p][c]]++; lst = ch[p][c];
        }
        inline LL Solve(LL rnt = 0) {
            for(register int i = cnt; i; i--) 
                size[fail[i]] += size[i], rnt = max(rnt, 1ll * len[i] * size[i]);
            return rnt;
        }
    } pam;
    
    int main() {
        scanf("%s", s + 1);
        for(register int i = 1; s[i]; i++) pam.Insert(s[i] - 'A', i, s);
        cout << pam.Solve();
        return 0;
    }