bzoj 3670 动物园

水题~~！

　　题目链接：bzoj 3670

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：在跑 KMP 的时候直接加一个限制：“(j+1)必须 ≤ i/2 ”就可以了。这为什么是对的呢？因为如果(j+1)比 i/2 大的话，(j+2)也一定比 (i+1)/2 大，所以 j 停留在这个位置没有意义，那么直接让 j=Next[j] 就好了。另外因为要求出所有满足要求的串的数量，所以我们还要维护一个数组表示以 i 为结尾的前缀有多少个前缀等于后缀就可以求出答案了。

　　我思故我在：水题。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
char ap[1000100];
int num[1000100];
int next[1000100];
int modd=1000000007;
int work()
{
	next[1]=0;
	num[1]=0;
	num[0]=-1;
	long long  ans=1;
	int k=0,j=0,lena=strlen(ap+1);
	for(int i=2;i<=lena;i++)
	{
		while(k&&ap[k+1]!=ap[i]) k=next[k];
		if(ap[k+1]==ap[i]) k++;
		next[i]=k,num[i]=num[k]+1;
		while(j&&(ap[j+1]!=ap[i]||(j+1)>i/2)) j=next[j];
		if(ap[j+1]==ap[i]) j++;
		ans=(ans*(num[j]+2))%modd;
	}
	return ans;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%s",ap+1);
		printf("%d\n",work());
	}
	return 0;
}