Ryan_<

题外话：我当时是看这道题题面理解fail数组含义的：

对于字符串S的前i个字符构成的子串，既是它的后缀又是它的前缀的字符串中，它本身除外(该子串一定既是后缀又是前缀，不算入答案)，最长的长度

题意：

求字符串的num数组，输出∏(i=1~L) (num[i]+1)%1000000007

num[i]:对于字符串S的前i个字符构成的子串，既是它的后缀同时又是它的前缀，且该后缀与前缀不重叠的字符串的数量。

分析：

朴素做法30%：O（n^2）

预处理出每个子串的hash值，求num[i]时枚举该长度，利用哈希值O（1）判断两子串是否相等。

const int N=(int)1e3+10;
int n,num[N];
char s[N];
LL ha[N][N],ans;
void hash(int id)
{
	ha[id][id-1]=0;
	for(int i=id;i<=n;i++){
		ha[id][i]=ha[id][i-1]*(LL)27+(LL)s[i]-'a'+1;
	}
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("zoo.in","r",stdin);
	#endif
	int tt=read();
	while(tt--){
		ans=1LL;mec(num,0);mec(ha,0);
		scanf("%s",s+1);
		n=strlen(s+1);
		F(i,1,n) hash(i);
		F(i,1,n){
			F(j,1,i/2) if(ha[1][j]==ha[i-j+1][i]) num[i]++;
			ans=ans*(LL)(num[i]+1)%MOD;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

50%：

我们的目标是要线性出解，一定与fail数组建立联系。

怎么表示这种关系呢？类似AC自动机中的，构建一棵fail树：

每个前缀i作为一个状态（节点），通过fail指针连接，构成一棵0为根的树，每个节点指向的父亲状态所表示的字符串均为该节点表示字符串的最长的一个后缀。父节点满足“既是它的后缀同时又是它的前缀”，但需要不重叠，就要沿着fail指针往上找。

转化为树的问题：

给定一棵树，求每个节点v到根路径上标号i<=v/2的节点数（不包括根节点）。

一条路径上，从叶到根的点的编号时单调的（由定义），“递归地”找到最近的祖先节点累计答案即可！

const int N=(int)1e6+10;
int n,f[N],cnt[N];LL ans;
char s[N];
void getFail()
{
	int j=0;f[1]=0;
	cnt[0]=0,cnt[1]=1;
	for(int i=2;i<=n;i++){
		int k=0;
		while(j&&s[i]!=s[j+1]) j=f[j];//k++;
		if(s[i]==s[j+1]) j++;
		f[i]=j;//cnt[i]=k-1;
		cnt[i]=cnt[j]+1;
	}
}
void solve()
{
	for(int i=2;i<=n;i++){
		int j=f[i];
		while(j*2>i) j=f[j];//路径上的结点编号是单调的!
		ans=ans*(LL)(cnt[j]+1)%MOD;
	}
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("zoo2.in","r",stdin);
	#endif
	int tt=read();
	while(tt--){
		mec(f,0);mec(cnt,0);ans=1LL;
		scanf("%s",s+1);
		n=strlen(s+1);
		getFail();//建出fail树
//		F(i,1,n) cout<<f[i]<<' ';cout<<endl;
		solve();//fail树自下向上统计答案
		printf("%d\n",ans);
	}
	return 0;
}

100%：

但是上面的代码TLE了！发现树高无法保证，在存在循环节情况下极可能退化成链！而出题人的数据是循环串+其余字母的形式，并且全都是！

良（sang）心（xin）数（bing）据（kuang）！

一个解决方法是，在树上走，用之前得到的j更新当前的j，而非用f[i]重新做。

void solve()
{
	int j=0;
	for(int i=2;i<=n;i++){
		while(j&&s[i]!=s[j+1]) j=f[j];
		if(s[i]==s[j+1]) j++;
		while(j*2>i) j=f[j];
		ans=ans*(LL)(cnt[j]+1)%MOD;
	}
}

fullpower神牛直接建了一棵树，维护栈。

void dfs(int u){
    ans=1ll*ans*(cnt+1)%mo; int t;
    for(int i=first[u];i;i=nxt[i]){
        st[++top]=v[i]; t=cnt;
        while(st[cnt+1]*2<=v[i]) cnt++;
        dfs(v[i]);
        --top; cnt=t;
    }
}
int main(){
    scanf("%d",&q);
    while(q--){
        scanf("%s",ch+1); n=strlen(ch+1);
        getnext();
        for(int i=0;i<=n;i++) first[i]=0; tot=0;
        for(int i=1;i<=n;i++) addedge(next[i],i);
        ans=1,top=cnt=0;
        dfs(0);
        printf("%d\n",ans);
    }
    return 0;
}