「NOI2014」动物园

link : https://loj.ac/problem/2246

水水KMP

#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
using namespace std;
const int ha=1000000007;
char s[maxn];
int f[maxn],g[maxn];
int n,T;

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%s",s),n=strlen(s);
		int j=0,k=0,ans=1;
		f[0]=f[1]=0,g[1]=1;
		
		for(int i=1;i<n;i++){
			while(j&&s[j]!=s[i]) j=f[j];
			if(s[j]==s[i]) j++;
			f[i+1]=j,g[i+1]=g[f[i+1]]+1;
			
			while(k&&(s[k]!=s[i]||(k<<1)>=i)) k=f[k];
			if(s[k]==s[i]) k++;
			ans=ans*(ll)(g[k]+1)%ha;
		}
		
		printf("%d
",ans);
	}
	
	return 0;
}