PAM（回文自动机/回文树）

一个由小写字母构成的字符串 \(s\)，对于 \(s\) 的每个位置，求出以该位置结尾的回文子串个数。
这个字符串被进行了加密，除了第一个字符，其他字符都需要通过上一个位置的答案来解密，强制在线。

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 5e5 + 10;
char s[N];
LL n, k;
struct PAM{
	LL tr[N][26], fail[N], len[N], cnt[N], idx, last;
	PAM(){
		fail[0] = 1, fail[1] = 1;
		len[1] = -1;
		idx = 1;
	}
	void insert(char c, LL i){
		LL p = get_fail(last, i);
		if (!tr[p][c - 'a']){
			fail[ ++ idx] = tr[get_fail(fail[p], i)][c - 'a'];
			tr[p][c - 'a'] = idx;
			len[idx] = len[p] + 2;
			cnt[idx] = cnt[fail[idx]] + 1;
		}
		last = tr[p][c - 'a'];
	}
	LL get_fail(LL u, LL i){
		while(i - len[u] - 1 < 0 || s[i - len[u] - 1] != s[i]){
			u = fail[u];
		}
		return u;
	}
}pam;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin >> s;
	n = strlen(s);
	for (int i = 0; i < n; i ++ ){
		s[i] = (s[i] - 'a' + k) % 26 + 'a';
		pam.insert(s[i], i);
		k = pam.cnt[pam.last];
		cout << k << " \n"[i == n - 1];
	}
	return 0;
}