题解
枚举所有的回文串
注意，本质不同的回文串最多只有 ∣S∣个
在这些回文串中，有一些是满足要求的，我们对这些串打上标记
首先跑一个 Manacher，然后枚举中间点，先从最大半径的回文串开始枚举，直到枚举的串之前出现过
在枚举的过程中， check 每个回文串是否满足要求，满足的打上标记，然后是最关键的部分，建图
根据枚举的顺序建立有向图，其实就是增加一条链
上面这个过程，用 Hash 判断重复，复杂度是线性的
为什么要这样做？
例如，枚举到某一个中间点，它枚举的回文串如图
其中，满足条件的为绿色底***r> 每次枚举一个中间点，实际上就是增加一条链
我们在新加入的链的顶端 +1 , 表明该顶点下面的所有儿子都将出现一次，其正确性是显然的
图全部建完之后，根据拓扑顺序，将每个顶点的值向儿子传递，同时保留自己的值
搞完之后，每个回文串出现的次数就已经确定了
最后一步，只关注之前打过标记的回文串，统计答案即可
代码
#include<bits/stdc++.h>
#define N 300010
#define M N<<0
#define INF 0x3f3f3f3f
#define eps 1e-10
// #define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%lld",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
gp_hash_table<LL,int>mp;
char x[N],ss[N<<1];
struct node{int x,y;}w[N];
int la[N],in[N],q[N],r[N<<1],len[N],num[N],fg[N],ans[N],lin_t,str_t,slen,cnt;
typedef pair<int,int> pi;
pi v[N<<1];
LL p[N],pp[N],hs[N],sh[N],hss[N],shh[N];
void pre(){
slen=strlen(x+1); lin_t=cnt=0; mp.cl();
memset(ans,0,sizeof(int)*(slen+3));
for(int i=1;i<=slen;i++)
hs[i]=(hs[i-1]*1331+x[i])%mod,
hss[i]=(hss[i-1]*9997+x[i])%P,
sh[i]=(sh[i-1]*1331+x[slen-i+1])%mod,
shh[i]=(shh[i-1]*9997+x[slen-i+1])%P;
}
inline void add(int x,int y){
w[++lin_t]=node{y,la[x]};
la[x]=lin_t;
}
inline LL cal(LL *h,LL *hh,int x,int y){
LL t1=(h[y]-h[x-1]*p[y-x+1]%mod+mod)%mod,
t2=(hh[y]-hh[x-1]*pp[y-x+1]%P+P)%P;
return t1<<30|t2;
}
int Init(){
int len=strlen(x+1);
ss[0]='$';ss[1]='#';
int j=2;
for (int i=1;i<=len;i++)ss[j++]=x[i],ss[j++]='#';
ss[j]='\0';
return j;
}
void Manacher(){
int len=Init();
int p,mx=0;
for (int i=1;i<len;i++) {
if (i<mx) r[i]=min(r[2*p-i],mx-i);else r[i]=1;
while (ss[i-r[i]]==ss[i+r[i]]) r[i]++;
if (mx<i+r[i])p=i,mx=i+r[i];
}
str_t=0;
for (int i=2;i<len;i++) {
if (ss[i]=='#' && r[i]==1) continue;
int x=i/2-r[i]/2+1,y=i/2+r[i]/2-!(i&1);
v[str_t++]=pi(x,y);
}
for(int i=0;i<len+3;i++) r[i]=0;
}
inline bool check(int l,int r){
if (cal(hs,hss,l,r)!=cal(sh,shh,slen-r+1,slen-l+1)) return false;
if (cal(hs,hss,l,(l+r)>>1)!=cal(sh,shh,slen+1-((l+r)>>1),slen+1-l)) return false;
return true;
}
namespace IO{
struct Ostream_fwrite{
#define BUF_SIZE 100000
#define OUT_SIZE 100000
char *buf,*p1,*pend;
Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
void out(char ch){
if (p1==pend){
fwrite(buf,1,BUF_SIZE,stdout);p1=buf;
}
*p1++=ch;
}
void print(int x){
static char s[15],*s1;s1=s;
if (!x)*s1++='0';if (x<0)out('-'),x=-x;
while(x)*s1++=x%10+'0',x/=10;
while(s1--!=s)out(*s1);
}
void print(char *s){while (*s)out(*s++);}
void flush(){if (p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
~Ostream_fwrite(){flush();}
}Ostream;
inline void print(int x){Ostream.print(x);}
inline void print(char *s){Ostream.print(s);}
inline void flush(){Ostream.flush();}
};
using namespace IO;
int main(){
p[0]=1; pp[0]=1;
for(int i=1;i<N;i++) p[i]=p[i-1]*1331%mod,
pp[i]=pp[i-1]*9997%P;
while(~scanf("%s",x+1))
{
pre();
Manacher();
for(int i=0;i<str_t;i++){
int l=v[i].fi,r=v[i].se,k=0;
while(l<=r){
LL tm=cal(hs,hss,l,r);
int t=mp[tm];
if(t){ q[++k]=t; break;}
mp[tm]=++cnt;
q[++k]=cnt;
if (check(l,r)) fg[cnt]=1;
len[cnt]=r-l+1;
l++;r--;
}
if (k) num[q[1]]++;
for(int i=1;i<k;i++) add(q[i],q[i+1]),in[q[i+1]]++;
}
int t=0, h=0;
for(int i=1;i<=cnt;i++) if (!in[i]) q[++t]=i;
while(h<t){
h++; int x=q[h];
for(int j=la[x];j;j=w[j].y){
num[w[j].x]+=num[x];
in[w[j].x]--; if (!in[w[j].x]) q[++t]=w[j].x;
}
}
for (int i=1;i<=cnt;i++) if (fg[i]) ans[len[i]]+=num[i];
print(ans[1]);
for (int i=2;i<=slen;i++)
Ostream.out(' '),print(ans[i]);
Ostream.out('\n');
for(int i=1;i<=cnt;i++) in[i]=num[i]=la[i]=len[i]=fg[i]=0;
}
}
京公网安备 11010502036488号