NOI2014 动物园

超级好的题，需要自己动一下脑子才不超时.
我们首先算出包含自己本身的并且有重复的num1[]来然后第二波kmp的时候进行进一步的失配指针偏移

if(j<i/2)
j=nex[j];

这样能够保证我们的j是不重复的j然后把之前的num1数组按照格式乘起来即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll nex[1000005],mod=ll(1e9)+7,num[1000005];
char s[1000005];
int main()
{
	ll t;
	scanf("%lld",&t);
	while(t--)
	{
		memset(nex,0,sizeof(nex));
		memset(num,0,sizeof(num));
		scanf("%s",s+1);
		ll len=strlen(s+1);
		ll j=0,ans=1;
		num[0]=0;
		num[1]=1;
		for(int i=2;i<=len;i++)
		{
			while(j&&s[i]!=s[j+1])
			j=nex[j];
			if(s[i]==s[j+1])
			j++;
			nex[i]=j;
			num[i]=num[j]+1;
		}
		j=0;
		for(int i=2;i<=len;i++)
		{
			while(j&&s[i]!=s[j+1])
			j=nex[j];
			if(s[i]==s[j+1])
			j++;
			while(j>i/2)
			j=nex[j];
			ans=ans%mod*(num[j]+1)%mod;
			ans%=mod;
		}
		printf("%lld\n",ans%mod);
	}
}