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; }