Problem Description
You are given a string
S=s1s2..s|S| containing only lowercase English letters. For each integer i∈[1,|S|] , please output how many substrings slsl+1...sr satisfy the following conditions:
∙ r−l+1 equals to i.
∙ The substring slsl+1...sr is a palindrome string.
∙ slsl+1...s⌊(l+r)/2⌋ is a palindrome string too.
|S| denotes the length of string S.
A palindrome string is a sequence of characters which reads the same backward as forward, such as madam or racecar or abba.
∙ r−l+1 equals to i.
∙ The substring slsl+1...sr is a palindrome string.
∙ slsl+1...s⌊(l+r)/2⌋ is a palindrome string too.
|S| denotes the length of string S.
A palindrome string is a sequence of characters which reads the same backward as forward, such as madam or racecar or abba.
Input
There are multiple test cases.
Each case starts with a line containing a string S(1≤|S|≤3×105) containing only lowercase English letters.
It is guaranteed that the sum of |S| in all test cases is no larger than 4×106.
Each case starts with a line containing a string S(1≤|S|≤3×105) containing only lowercase English letters.
It is guaranteed that the sum of |S| in all test cases is no larger than 4×106.
Output
For each test case, output one line containing
|S| integers. Any two adjacent integers are separated by a space.
Sample Input
abababa
Sample Output
7 0 0 0 3 0 0
题意:给你一个字符串 要你输出长度分别为1~len的good回文串的个数(good回文串定义为 当前是回文串 且他的一半也是回文串)
思路:我们首先用回文自动机把回文串都记录下来 然后字符串hash判断是否两半是否相等
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long const int inf = 0x3f3f3f3f; const int N = 4e5+7; const ll mod = 998244353; using namespace std; ull hash1=233; ull ha[N],pp[N]; ull getha(int l,int r){ if(l==0) return ha[r]; return ha[r]-ha[l-1]*pp[r-l+1]; } struct Palindromic_Tree{ int next[N][30]; //节点之间连边 int fail[N]; //适配指针 表示当前回文串的最长回文后缀 int len[N]; //当前回文串的长度 int cnt[N]; //回文串的个数 int id[N]; //回文串的右端点 int S[N]; int last,n,p; int newnode(int l){//新建节点 for(int i=0;i<26;i++) next[p][i]=0;//新建的节点为p,先消除它的子节点 cnt[p]=0; len[p]=l; return p++;//勿打成++p,因为此节点为p,我们应返回p } void init(){ last=n=p=0; newnode(0); newnode(-1); S[0]=-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-='a'; S[++n]=c; int po=get_fail(last); if(!next[po][c]){ int now=newnode(len[po]+2); fail[now]=next[get_fail(fail[po])][c]; next[po][c]=now; } last=next[po][c]; cnt[last]++; id[last]=n; } void count(){ for(int i=p-1;i>=0;i--) cnt[fail[i]]+=cnt[i]; } }pat; ll ans[N]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); pp[0]=1; for(int i=1;i<N;i++) { pp[i]=hash1*pp[i-1]; } string s; while(cin>>s){ memset(ans,0,sizeof(ans)); pat.init(); int len=s.length(); for(int i=0;i<len;i++){ pat.add(s[i]); } ha[0]=s[0]; for(int i=1;i<len;i++) ha[i]=ha[i-1]*hash1+s[i]; pat.count(); for(int i=2;i<pat.p;i++){ int l=pat.id[i]-pat.len[i]; int r=pat.id[i]-1; int mid=(l+r)>>1; if((r-l+1)&1){ if(getha(l,mid)==getha(mid,r)){ ans[pat.len[i]]+=pat.cnt[i]; } }else{ if(getha(l,mid)==getha(mid+1,r)){ ans[pat.len[i]]+=pat.cnt[i]; } } } for(int i=1;i<=len;i++){ if(i==1) cout<<ans[i]; else cout<<" "<<ans[i]; } cout<<endl; } return 0; }