BZOJ3670：[NOI2014]动物园

浅谈(KMP)：https://www.cnblogs.com/AKMer/p/10438148.html

题目传送门：https://lydsy.com/JudgeOnline/problem.php?id=3670

假设(step_i)是这么造出来的：

step[0]=1;for(int i=1;i<=n;i++)step[i]=step[nxt[i]]+1;

(step_i)表示在(while(i)i=nxt_i;)这句话里面(i)出现过的权值种类。

那么(num_i)就是在(while(i)i=nxt_i)中不超过(i/2)的最大的位置的(step)，我们做两遍(KMP)，第一遍求(nxt)和(step)，第二遍求的时候强行让(j)不超过(i/2)然后把(step_j)累乘到(ans)里面即可。

时间复杂度：(O(n))

空间复杂度：(O(n))

代码如下：

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=1e6+5,pps=1e9+7;

int n,ans;
char s[maxn];
int nxt[maxn],step[maxn];

int read() {
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
	return x*f;
}

void make_nxt_step() {
	for(int j=0,i=2;i<=n;i++) {
		while(j&&s[j+1]!=s[i])j=nxt[j];
		if(s[j+1]==s[i])j++;nxt[i]=j,step[i]=step[j]+1;
	}
}

void make_ans() {
	for(int j=0,i=2;i<=n;i++) {
		while(j&&s[j+1]!=s[i])j=nxt[j];
		if(s[j+1]==s[i])j++;
		while(j>i/2)j=nxt[j];
		ans=1ll*ans*step[j]%pps;
	}
}

int main() {
	int T=read();
	step[0]=1,step[1]=2;
	while(T--) {
		scanf("%s",s+1);
		n=strlen(s+1);
		make_nxt_step();
		ans=1,make_ans();
		printf("%d
",ans);
	}
	return 0;
}