回文自动机 PAM（回文树）

应用：

1. 本质不同的回文串个数：$idx-2$；
2. 回文子串出现次数。

对于一个字符串 $s$，它的本质不同回文子串个数最多只有 $|s|$ 个，那么，构造 $s$ 的回文树的时间复杂度是 $O(|s|)$。

const int MAXN = 5e5 + 10;
const int SIGMA = 26;

struct PAM {
    int tr[MAXN][SIGMA];
    int fail[MAXN], len[MAXN];
    int cnt[MAXN]; // 以当前节点为后缀的回文串个数
    int num[MAXN]; // 本质不同回文串在整个文本中出现的总次数
    int s[MAXN];   // 字符流（1-based），s[0] 为哨兵
    int tot, last, n;

    void init() {
        for (int i = 0; i <= tot; i++) {
            memset(tr[i], 0, sizeof(tr[i]));
            fail[i] = len[i] = cnt[i] = num[i] = 0;
        }
        s[0] = -1; // 哨兵：避免 get_fail 越界检查
        len[0] = 0, fail[0] = 1;  // 偶根 (node 0)
        len[1] = -1, fail[1] = 0; // 奇根 (node 1)
        tot = 1;                  // 根节点占用 0 与 1
        last = 0;
        n = 0;
    }

    int get_fail(int u) {
        while (s[n - len[u] - 1] != s[n]) u = fail[u];
        return u;
    }

    void insert(char c) {
        s[++n] = c - 'a';
        int u = get_fail(last);
        if (!tr[u][s[n]]) {
            int v = ++tot;
            len[v] = len[u] + 2;
            fail[v] = tr[get_fail(fail[u])][s[n]];
            cnt[v] = cnt[fail[v]] + 1;
            tr[u][s[n]] = v;
        }
        last = tr[u][s[n]];
        num[last]++;
    }

    // 建树结束后必须调用：沿 Fail 树拓扑更新出现次数
    void count() {
        for (int i = tot; i >= 2; i--) {
            num[fail[i]] += num[i];
        }
    }

    // 本质不同回文子串总数
    int distinct_palindromes() {
        return tot - 1;
    }
} pam;