回文树总结

首先，回文自动机就是回文树。

不愧是\(\texttt{tham}\)，在\(CSP\)模拟赛里面考\(PAM\)

问题引入

求一个由小写字母'a'-'z'构成的串的本质不同的回文子串数量。

问题解决

暴力

首先考虑把每一个子串枚举出来，然后判断是不是回文串再把它\(Hash\)进\(map\)或者是\(Hash-table\)里面。复杂度\(\Theta(n^3)\)

暴力优化

想一想判断是不是回文串可以通过正反两遍\(Hash\)得到。复杂度\(\Theta(n^2)\)。

manacher

考虑manacher的过程是不是可以求出所有的回文串，预处理\(Hash\)值然后用\(map\)或者\(Hash-table\)可以做到\(\Theta(n)\)或\(\Theta(nlogn)\)

PAM

这就是我们要说的算法——回文自动机。

形态

构造

代码实现

int tot=1,last;
char s[N];
struct node{
    int son[26],len,ff;
}t[N<<1];
void extend(int c,int n){
    int p=last;
    while(s[n]!=s[n-t[p].len-1])p=t[p].ff;
    if(!t[p].son[c]){
        int np=++tot,k=t[p].ff;t[np].len=t[p].len+2;
        while(s[n]!=s[n-t[k].len-1])k=t[k].ff;
        t[np].ff=t[k].son[c];
        t[p].son[c]=np;ans++;
    }
    last=t[p].son[c];
}