lg2375 发表于 2018-12-11 | 分类于 题解 | 阅读数 次 链接:lg2375 题解 如果不考虑重叠,nm数组可以在求nxt数组的时候一起求出来。考虑重叠的话只需要再用自己匹配自己一次,重叠的部分不乘就ok 12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define ll long longusing 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;}