lg2375

链接:lg2375

题解

  • 如果不考虑重叠,nm数组可以在求nxt数组的时候一起求出来。考虑重叠的话只需要再用自己匹配自己一次,重叠的部分不乘就ok
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define ll long long
using namespace std;
const int N=1e6+7;
const ll mod=1e9+7;
char str[N];
int len,T,nm[N],nxt[N];
inline void pre(){
int k=0;nm[1]=1;
rep(i,2,len){
while(k&&str[i]!=str[k+1])k=nxt[k];
if(str[i]==str[k+1])k++;
nxt[i]=k;
nm[i]=nm[k]+1;
}
}
inline void solve(ll &ans){
int k=0;
rep(i,2,len){
while(k&&str[i]!=str[k+1])k=nxt[k];
if(str[i]==str[k+1])k++;
while(2*k>i)k=nxt[k];
ans=ans*(nm[k]+1)%mod;
}
}
int main(){
scanf("%d",&T);
while(T--&&~scanf("%s",str+1)){
ll ans=1;len=strlen(str+1);
memset(nxt,0,sizeof nxt);
pre();
solve(ans);
printf("%lld\n",ans);
}
return 0;
}