PAM Palindromic Automata

性质

1.本质不同(The location can be the same）The number of palindromic strings is equal to the number of nodes in the palindromic automaton − 2 ;
2.The number of occurrences of a palindrome is equal to the number of nodes in the subtree rooted at it lastsum of times;
3.The number of palindromes with different positions is equal to each node（除 even 和 odd）The sum of the occurrences of the corresponding palindrome;

功能

1.Find the number of essentially distinct palindromes
2.Find the number of times a string appears as a palindrome
3.以iThe sign character is the number of ending palindrome strings

#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]为iNo. node is the end
    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]++ Required to count the number of occurrences of a string
    }
    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:Count the number of all palindrome strings
    for (int i = 1; i <= pam.size; i++)
        ans += pam.cnt[i];
    printf("%d", ans);
    //op2:输出iThe number of palindromes at the end
    for (int i = 0; i < len; i++) {
    
        pam.insert(str[i] - 'a' + 1, i);
        printf("%d ", pam.cnt[pam.last]);
    }
    //op3:How many times a string appears,需要在buildwhen maintaining information
    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;
}