PAM 回文自动机

性质

1.本质不同(位置可以相同）的回文串数量等于回文自动机的节点数 − 2 ；
2.一个回文串出现的次数等于以之为根的子树的各节点作为 last的次数之和；
3.位置不同的回文串的数量等于各个节点（除 even 和 odd）对应的回文串出现的次数之和；

功能

1.求本质不同的回文串数量
2.求某个字符串作为回文串出现的次数
3.以i号字符为结尾的回文串个数

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
char str[maxn];
struct PAM {
    
    int size, last, r0, r1;
    int trie[maxn][26], fail[maxn], len[maxn], cnt[maxn];//cnt[last]为i号节点为结尾
    PAM() {
    
        r0 = size++, r1 = size++; last = r1;
        len[r0] = 0, fail[r0] = r1;
        len[r1] = -1, fail[r1] = r1;
    }
    void insert(int ch, int idx) {
    
        int u = last;
        while (str[idx] != str[idx - len[u] - 1])u = fail[u];
        if (!trie[u][ch]) {
    
            int cur = ++size, v = fail[u];
            len[cur] = len[u] + 2;
            for (; str[idx] != str[idx - len[v] - 1]; v = fail[v]);
            fail[cur] = trie[v][ch]; trie[u][ch] = cur;
            cnt[cur] = cnt[fail[cur]] + 1;
        }
        last = trie[u][ch];
        //cnt[last]++ 统计某个串出现次数时需要
    }
    void build(char* str) {
    
        int len = strlen(str);
        for (int i = 0; i < len; i++)
            insert(str[i] - 'a' + 1, i);
    }
}pam;
int main() {
    
    scanf("%s", str);
    pam.build(str);
    int len = strlen(str);
    long long ans = 0;
    //op1:统计所有回文串个数
    for (int i = 1; i <= pam.size; i++)
        ans += pam.cnt[i];
    printf("%d", ans);
    //op2:输出i号为结尾的回文串个数
    for (int i = 0; i < len; i++) {
    
        pam.insert(str[i] - 'a' + 1, i);
        printf("%d ", pam.cnt[pam.last]);
    }
    //op3:某个串出现多少次，需要在build的时候维护信息
    for (int i = pam.size; i >= 0; i--) {
    
        pam.cnt[pam.fail[i]] += pam.cnt[i];
        ans = max(ans, 1ll * pam.cnt[i] * pam.len[i]);
    }
   
    return 0;
}