模板 - 字符串 - 回文自动机

我好像有点明白了，字符串题目很多都是关心这个后缀。

struct PAM {
    char s[MAXN];
    int ch[MAXN][26];
    int fail[MAXN];
    int len[MAXN];
    int tot, top, last;

    void Init() {
        len[0] = 0;
        fail[0] = 1;
        len[1] = -1;
        fail[1] = 0;
        tot = 1;
        top = 0;
        last = 0;
        memset(ch[0], 0, sizeof(ch[0]));
        memset(ch[1], 0, sizeof(ch[1]));
    }

    int NewNode(int l) {
        int now = ++tot;
        memset(ch[tot], 0, sizeof(ch[tot]));
        len[now] = l;
        return now;
    }

    void Extend(char c) {
        s[++top] = c;
        c -= 'a';
        int u = last;
        while(s[pos - len[u] - 1] != s[pos])
            u = fail[u];
        if(ch[u][c] == 0) {
            int now = NewNode(len[u] + 2);
            int v = fail[u];
            while(s[pos - len[v] - 1] != s[pos])
                v = fail[v];
            fail[now] = ch[v][c];
            ch[u][c] = now;
        }
        last = ch[u][c];
    }
} pam;

模板 - 字符串 - 回文自动机

原文：https://www.cnblogs.com/KisekiPurin2019/p/12538934.html