hdu6599 求符合要求的子串的数目，要求为其本身为回文串，且其一半也是回文串。 回文自动机板子题。判一半可以马拉车，也可以hash预处理完了都是O(1)判断。
/* next[][]类似于字典树，指向当前字符串在两段同时加上一个字符 fail指针，类似于AC自动机，返回失配后与当前i结尾的最长回文串本质上不同的最长回文后缀 cnt[] 在最后统计后它可以表示形如以i为结尾的回文串中最长的那个串个数 num[] 表示以i结尾的回文串的种类数 len[] 表示以i为结尾的最长回文串长度 s[] 存放添加的字符 last 表示上一个添加的字符的位置 n 表示字符数组的第几位 p 表示树中节点的指针 */
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int N =3e5+50; ll ret[N]; char s[N]; char new_s[N*2]; int pi[N*2]; bool Check(int l,int r) { int len=r-l+1; if(pi[l+r+2]-1>=len)return true; return false; } bool check(int l,int r){ int len=r-l+1; if(len<=2) return true; else return Check(l,(l+r)/2); } struct Palindromic_Tree{ int nxt[N][30],fail[N],cnt[N]; int num[N],len[N],s[N],id[N]; int last,n,p; int newnode(int l){ memset(nxt[p],0,sizeof(nxt[p])); cnt[p]=num[p]=0; len[p]=l; return p++; } void init(){ p=0; newnode(0),newnode(-1); last=n=0; 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 cur=get_fail(last); if(!nxt[cur][c]){ int now=newnode(len[cur]+2); fail[now]=nxt[get_fail(fail[cur])][c]; nxt[cur][c]=now; num[now]=num[fail[now]]+1; } 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++){ if(check(id[i]-len[i],id[i]-1)){ ret[len[i]]+=cnt[i]; } } } }pam; int Init() { int len=strlen(s); new_s[0]='$'; new_s[1]='#'; int j=2; for(int i=0;i<len;i++) { new_s[j++]=s[i]; new_s[j++]='#'; } new_s[j]='\0'; return j; } void Manacher() { int len=Init(); int id; int mx=0; for(int i=1;i<len;i++) { if(i<mx) pi[i]=min(pi[2*id-i],mx-i); else pi[i]=1; while(new_s[i-pi[i]]==new_s[i+pi[i]]) pi[i]++; if(mx<i+pi[i]) { id=i; mx=+i+pi[i]; } } } int main() { while(~scanf("%s",s)){ memset(ret,0,sizeof(ret)); pam.init(); Init(); Manacher(); int len=strlen(s); for(int i=0;i<len;i++) { pam.add(s[i]); } pam.Count(); printf("%lld",ret[1]); for(int i=2;i<=len;i++) { printf(" %lld",ret[i]); } printf("\n"); } return 0; }hash处理
ll ret[N]; 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]; } bool check(int l, int r) { int len = r - l + 1; int mid = (l + r) >> 1; if (len & 1) return getha(l, mid) == getha(mid, r); else return getha(l, mid) == getha(mid + 1, r); } pp[0] = 1; for (int i = 1; i < N; i++) { pp[i] = hash1 * pp[i - 1]; } for (int i = 1; i < len; i++) { ha[i] = ha[i - 1] * hash1 + str[i]; }