题目：动物园
思路：
kmp。
就是把nxt求出来后再顺着nxt往前匹配，直到满足条件为止。
要设一个数组记录nxt为i时的公共前后缀数量。
注意查询时，要重复利用j，不然会TLE成50'。
代码：
50'代码：
#include<bits/stdc++.h>
using namespace std;#define md ((int)(1e9)+7)
#define maxn 1000000
#define maxm 1000000
#define read(x) scanf("%d",&x)char b[maxn+5];
int m;
int nxt[maxn+5];
int num[maxn+5];int main() {int T;read(T);while(T--) {scanf("%s",b+1);m=strlen(b+1);nxt[1]=0,num[1]=0;for(int i=2; i<=m; i++) {int j=nxt[i-1];while(b[i]!=b[j+1]&&j>0) {j=nxt[j];}if(b[i]==b[j+1]) nxt[i]=j+1,num[i]=num[j+1]+1;else nxt[i]=0,num[i]=0;}int ans=1;for(int i=1;i<=m;i++) {int x=nxt[i];while(x*2>i) x=nxt[x];if(b[i]==b[x]) ans=(long long)ans*(num[x]+2)%md;}printf("%d\n",ans);}return 0;
}
AC代码：
#include<bits/stdc++.h>
using namespace std;#define md ((int)(1e9)+7)
#define maxn 1000000
#define maxm 1000000
#define read(x) scanf("%d",&x)char b[maxn+5];
int m;
int nxt[maxn+5];
int num[maxn+5];int main() {int T;read(T);while(T--) {scanf("%s",b+1);m=strlen(b+1);nxt[1]=0,num[1]=0;for(int i=2; i<=m; i++) {int j=nxt[i-1];while(b[i]!=b[j+1]&&j>0) {j=nxt[j];}if(b[i]==b[j+1]) nxt[i]=j+1,num[i]=num[j+1]+1;else nxt[i]=0,num[i]=0;}int ans=1,x=0;for(int i=2;i<=m;i++) {while(b[i]!=b[x+1]&&x>0) x=nxt[x];if(b[i]!=b[x+1]) continue;x++;while(x*2>i) x=nxt[x];ans=(long long)ans*(num[x]+2)%md;}printf("%d\n",ans);}return 0;
}
很久以前写得看不懂的代码——：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <cstring>
#include <map>
using namespace std;#define maxn 1000000
#define MOD 1000000007char a[maxn+5];
int num[maxn+5];
int nxt[maxn+5];int main() {int T;scanf("%d",&T);while(T--) {scanf("%s",a);int n=strlen(a);memset(num,0,sizeof(num));nxt[0]=-1;for(int i=0; i<n; i++) {int j=nxt[i];while(j>=0&&a[j]!=a[i]) {j=nxt[j];}nxt[i+1]=++j;num[i+1]=num[j]+1;}int i=0,j=0;long long s=1;while(i<n) {while (j!=-1&&a[j]!=a[i]) {j=nxt[j];}j++;while(j*2>i+1) {j=nxt[j];}s=s*(num[j]+1)%MOD;i++;}printf("%lld\n",s);}return 0;
}