题意
给定一个串,求各长度下,本质不同的回文串并且回文串的左右两个字串也是回文串的数量。
思路
题意比较绕,理顺下来就是在回文树的每个节点,求其节点对应回文串的一半是否也是回文串,如果是,则其对该节点的长度产生贡献, 判断其回文串的一半是否也为回文串可以用马拉车或者哈希,哈希相对好写一点。
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
const int mod = 998244353;
const int hs=31;
int ans[maxn], n;
char str[maxn];
typedef unsigned long long ull;
ull has[maxn], p[maxn];
ull Hash(int l, int r) { return has[r] - has[l-1]*p[r-l+1];}
bool check(int l, int r) {
int mid = l+r>>1, len = r-l+1;
if(len&1) return Hash(l, mid)==Hash(mid, r);
return Hash(l, mid)==Hash(mid+1, r);
}
struct Pam{
int len[maxn], cnt[maxn], num[maxn], id[maxn];
int nxt[maxn][26], fail[maxn], s[maxn];
int p, last, n;
int insert(int l) {
for (int i=0; i<26; ++i) nxt[p][i]=0;
cnt[p] = fail[p] = 0;
len[p] = l;
return p++;
}
void init() {
p=n=last=0;
insert(0), insert(-1);
// memset(cnt, 0, sizeof(cnt));C
fail[0]=1;
s[n]=-1;
}
int getFail(int x) {
while(s[n-len[x]-1]!=s[n]) x=fail[x];
return x;
}
void add(int c) {
c-='a';
s[++n] = c;
int cur = getFail(last);
// cout << cur << " ";
if(!nxt[cur][c]) {
int now = insert(len[cur]+2);
fail[now] = nxt[getFail(fail[cur])][c];
nxt[cur][c] = now;
num[now] = num[fail[now]]+1;
}
// cout << fail[nxt[cur][c]] << endl;
last = nxt[cur][c];
++cnt[last];
id[last] = n;
}
void count() {
for (int i=p-1; i>=0; --i) cnt[fail[i]] += cnt[i];
// for (int i=2; i<p; ++i) printf("%d ", cnt[i]); puts("");
// cout << p << endl;
for (int i=2; i<p; ++i) {
if(check(id[i]-len[i]+1, id[i]))
ans[len[i]] += cnt[i];
}
}
}pam;
int main(){
while(scanf("%s", str+1)==1) {
pam.init();
n = strlen(str+1);
for (int i=1; i<=n; ++i) {
pam.add(str[i]);
ans[i] = 0;
}
p[0] = 1;
for (int i=1; i<=n; ++i) {
p[i] = p[i-1]*hs;
has[i] = has[i-1]*hs + (str[i]-'a');
}
pam.count();
for (int i=1; i<=n; ++i)
printf("%d ", ans[i]);
puts("");
}
return 0;
}