https://vjudge.net/problem/UESTC-1999

题意

对于一个初始为空的字符串S，你可以进行以下两种操作：

1. 在S的末尾加一个小写字母。

2. 移除S的最后一个字母。

每进行完一个操作，你需要统计S中回文串的数量。

分析

模板题，每次跑一遍回文树

#include<cstdio>
#include<string.h>
#include<cstring>
#include<string>
using namespace std;

const int MAXN = 1e4 + 5;
const int N = 26;

const int maxn = 1e4 + 5;
const int ALP = 26;

struct PAM {
    int next[maxn][ALP];
    int fail[maxn];
    int cnt[maxn];
    int num[maxn];
    int len[maxn];
    int s[maxn];
    int last, n, p;

    int newnode(int l) {
        for (int i = 0; i<ALP; i++)
            next[p][i] = 0;
        cnt[p] = num[p] = 0;
        len[p] = l;
        return p++;
    }
    void init() {
        p = 0;
        newnode(0);
        newnode(-1);
        last = 0;
        n = 0;
        s[n] = -1;
        fail[0] = 1;
    }
    int get_fail(int x) {
        while (s[n - len[x] - 1] != s[n]) x = fail[x];
        return x;
    }
    void add(int c) {
        c = c - 'a';
        s[++n] = c;
        int cur = get_fail(last);
        if (!next[cur][c]) {
            int now = newnode(len[cur] + 2);
            fail[now] = next[get_fail(fail[cur])][c];
            next[cur][c] = now;
            num[now] = num[fail[now]] + 1;
        }
        last = next[cur][c];
        cnt[last]++;
    }
    void count() {
        for (int i = p - 1; i >= 0; i--)
            cnt[fail[i]] += cnt[i];
    }
}tree;


char s[MAXN];
string snew;
int q, ans[MAXN];

int main() {
    scanf("%d", &q);
    scanf("%s", s);
    for (int i = 0; i < q; i++) {
        if (s[i] == '-') snew.pop_back();
        else snew.push_back(s[i]);
        tree.init();
        for (int j = 0; j < snew.size(); j++) {
            tree.add(snew[j]);
        }
        tree.count();
        for (int j = 2; j < tree.p; j++) {
            ans[i] += tree.cnt[j];
        }
    }
    for (int i = 0; i < q; i++) {
        printf("%d ", ans[i]);
    }
    return 0;
}