一篇 PAM 的题解
前置知识
- 回文自动机 PAM
介绍详见 OI Wiki 中的描述，此处不作赘述。
思路分析
分两种情况讨论：
- 当前字符是小写字母时，按照题意插入此字符，然后统计。
- 当前字符是
-时，删除字符串末尾的字符，然后统计。
构建回文自动机，按照题意模拟即可。
删除操作
由于 PAM 结点只增不减（保证 fail 指针有效及结点复用），删除时采用状态回滚策略，通过维护历史栈恢复上一状态。
复杂度分析
- 时间复杂度：
O(Q) 。PAM 的get_fail跳转次数是均摊O(1) 的，删除操作仅为栈操作O(1) ，不存在真正意义上的O(q^2) 最坏情况。 - 空间复杂度：
O(Q) 。PAM 结点数最多为Q+2 ，栈空间也为O(Q) 。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long // 十年OI一场空，不开long long见祖宗
const int N = 10010;
const int AL = 26;
struct PAM {
int n, last, tot;
int tp; // 回文子串总数量
int len[N], fail[N];
int num[N]; // 以该节点结尾的回文后缀个数
int nextt[N][AL];
vector<int> lh; // last历史栈，回滚用
vector<int> th; // tp历史栈，回滚用
vector<int> ch;
int s[N];
PAM() {
init();
}
void init() {
n = 0; last = 0; tot = 2; tp = 0;
len[0] = 0; fail[0] = 1;
len[1] = -1; fail[1] = 1;
num[0] = num[1] = 0;
s[0] = -1; // 哨兵，防止get_fail越界
memset(nextt, 0, sizeof(nextt));
lh.clear(); th.clear(); ch.clear();
lh.push_back(last);
th.push_back(tp);
}
int get_fail(int x) {
while (s[n - len[x] - 1] != s[n]) {
x = fail[x];
}
return x;
}
void add(int c) {
s[++n] = c;
int cur = get_fail(last);
if (!nextt[cur][c]) {
int now = tot++;
len[now] = len[cur] + 2;
fail[now] = (len[now] == 1) ? 0 : nextt[get_fail(fail[cur])][c];
nextt[cur][c] = now;
num[now] = num[fail[now]] + 1;
}
last = nextt[cur][c];
tp += num[last];
ch.push_back(c);
lh.push_back(last);
th.push_back(tp);
}
void remove() {
if (n == 0) {
return;
}
ch.pop_back();
lh.pop_back();
th.pop_back();
last = lh.back();
tp = th.back();
n--;
}
int get_total() {
return tp;
}
};
PAM p;
signed main() { // 注意此处main函数类型不能用int
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int q;
cin >> q;
while (q--) {
char op;
cin >> op;
if (op != '-') {
p.add(op - 'a');
}
else {
p.remove();
}
cout << p.get_total() << ' ';
}
return 0;
}