时间限制3.5s，空间512MB
题目描述
T组数据，每组给出一段字符串，求其中不同的回文串有几个。
数据范围
T<=10,len<=1e6.
题目解析
正解是回文自动机，答案为自动机中节点数-2，但是并不会。
考场上写了一个花里胡哨的马拉车加trie。
跑马拉车时若当前直接匹配到的地方为cj[i]，则用并查集加二分查找找出该点所对应的trie节点，之后继续匹配时向trie中加数，答案是trie中非‘#’字符个数。复杂度O(len *loglen*t).
爆炸了100——20.无法debug.
发现其他人暴力过了。于是可以在匹配完成后如果该串长度大于cj[zai*2-i]，则暴力往trie中加入该回文串（除第一位外不加‘#’），复杂度O(玄学)。答案即为trie中节点个数-1（多一个‘#’）
莫得办法。
代码如下：
#include<bits/stdc++.h> using namespace std; const int N=2e6+5; int t,cnt,dao,n,cj[N],r,zai,ans,now,dui[200],dapan; char c[N],s[N]; struct pigu { int er[29]; }tier[N<<1]; inline int read() { char c=getchar(); int x=0,f=1; while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();} while(isdigit(c)) {x=(x<<3)+(x<<1)+c-'0';c=getchar();} return x*f; } //inline int pan(int &x) //{ // if(!x) x=++cnt,dapan++; // return x; //} //inline int findfa(int x) //{ // if(fa[x]==x) return x; // fa[x]=findfa(fa[x]); // return fa[x]; //} //inline int find(int zn,int hd) //{ // int l=0,r=ves[zn].size()-1,zd=0; // while(l<=r) // { // int mid=(l+r)>>1; // if(ves[zn][mid]>=hd) r=mid-1,zd=mid; // else l=mid+1; // } // if(zd==0) return ve[vef[zn][zd]][hd-1]; // else return ve[vef[zn][zd]][hd-ves[zn][zd-1]-1]; //} //queue <int> que; //inline void qingkongtier() //{ // que.push(0); // while(!que.empty()) // { // int now=que.front(); // que.pop(); // for(int i=0;i<=dui['$'];i++) if(tier[now].er[i]) // { // que.push(tier[now].er[i]); // tier[now].er[i]=0; // } // } //} inline void insert(int now,int you) { int nu=0;if(c[now]=='#') nu=tier[nu].er[dui['#']]; for(int i=now;i<=now+you-1;i++) { if(c[i]=='#') continue; if(tier[nu].er[dui[c[i]]]==0) { tier[nu].er[dui[c[i]]]=++cnt; nu=tier[nu].er[dui[c[i]]]; memset(tier[nu].er,0,sizeof(tier[nu].er)); } else nu=tier[nu].er[dui[c[i]]]; } } int main() { freopen("confusion.in","r",stdin); freopen("confusion.out","w",stdout); t=read(); for(int i='a';i<='z';i++) dui[i]=i-'a';dui['#']='z'-'a'+1;dui['$']='z'-'a'+2; while(t--) { scanf("%s",s+1); cnt=1;dao++;zai=r=0;ans=0; tier[0].er[dui['#']]=1; memset(tier[1].er,0,sizeof(tier[1].er)); memset(cj,0,sizeof(cj)); n=strlen(s+1);c[0]='$';c[1]='#'; for(int i=1;i<=n;i++) {c[i*2]=s[i];c[i*2+1]='#';} n=n*2+1;c[n+1]='%'; for(int i=1;i<=n;i++) { int sum=0;dapan=0; if(i<r) cj[i]=min(r-i,cj[zai*2-i]); cj[i]=max(cj[i],1); while(c[i+cj[i]]==c[i-cj[i]]) cj[i]++; if(cj[i]>cj[zai*2-i]||i>=r) insert(i,cj[i]); if(i+cj[i]>r) r=i+cj[i],zai=i; } memset(tier[0].er,0,sizeof(tier[0].er)); cout<<cnt-1<<" "; } fclose(stdin); fclose(stdout); return 0; } /* 3 aaaa mymom abba 2 ithinkifiamherehewillnotdie auutpppfotttoduergggepsekkssu */