初二那时候这题成功0分。
然而现在对于复杂度还是有点乱。。。
暴力做法的话。。显然就是使劲在fail树上跳，看fail链上有多少个<=长度/2的节点。
如果对于fail树上的节点，记录一下根到它的节点数的话。。每次查询的时候我们只要找到刚好<=长度/2的那个分界点就行了。
对于一条fail链，分界点显然是随着深度而单调的。。。所以每次从fail链最末的节点开始，把整条链都扒出来，利用分界点的单调性求解。
复杂度的话。。并不是严格O(n)...要看这些fail链有多少节点会被重复计算。
比方说。。字符串 aaaaaa.......如果后面有很多个节点的fail都指向那一坨'a'的末端的话。。。
似乎就会有很多重复计算，但实际上最末的那个'a'一定是分界点。
因为fail的大小的增长是线性的...每往后一位，fail的大小最多+1
所以大概复杂度就不用担心了吧= =
速度极慢，应该是比较丑的。。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #define ll long long 5 using namespace std; 6 const int maxn=1000233; 7 const ll modd=1000000007; 8 char s[maxn]; 9 int fail[maxn],sm[maxn],st[maxn],top; 10 int i,j,k,n,m,l; 11 ll an,ans[maxn]; 12 bool u[maxn]; 13 14 inline void getfail(int n){ 15 int i,p=0;fail[1]=0; 16 for(i=2;i<=n;i++){ 17 while(p&&s[p+1]!=s[i])p=fail[p]; 18 p+=s[p+1]==s[i],fail[i]=p; 19 } 20 } 21 int main(){ 22 int T;scanf("%d",&T); 23 for(int ii=1;ii<=T;ii++){ 24 25 scanf("%s",s+1); 26 // for(i=1;i<=1000000;i++)if(i&2)s[i]='b';else s[i]='a'; 27 s[0]='%';n=strlen(s)-1; 28 if(ii>1)memset(sm,0,(n+1)<<2),memset(u,0,n+1); 29 getfail(n); 30 for(i=1;i<=n;i++)sm[i]=sm[fail[i]]+1; 31 32 for(i=n;i;i--)if(!u[i]) 33 if((fail[i]<<1)<=i)u[i]=1,ans[i]=sm[fail[i]]; 34 else{ 35 for(st[top=1]=j=i;fail[j];st[++top]=(j=fail[j])); 36 l=top+1;st[top+1]=0; 37 for(j=top;j;j--){ 38 while((st[l-1]<<1)<=st[j])l--; 39 ans[st[j]]=sm[st[l]]; 40 u[st[j]]=1; 41 } 42 } 43 for(i=an=1;i<=n;i++){ 44 an*=ans[i]+1; 45 if(an>=modd)an%=modd; 46 // printf(" %d %lld ",i,ans[i]); 47 } 48 printf("%lld ",an); 49 } 50 return 0; 51 }