BZOJ3670
一开始想
O(n)
的算法，打半天是错的。 然后发现直接暴力翻就可以了。 那这样的话就先正常做
KMP
，然后求出“即是后缀又是前缀，且前缀与后缀可重叠的字符串数量
Numi
” 之后翻到一个最后的且长度为当前一半以内的位子
j
。numi=Numj
【代码】
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define N 1000005
#define mod 1000000007
#define INF 0x7fffffff
using namespace std;
typedef long long ll;
ll read()
{
ll x=
0,f=
1;
char ch=getchar();
while(!
isdigit(ch)){
if(ch==
'-') f=-
1;ch=getchar();}
while(
isdigit(ch)){x=(x<<
1)+(x<<
3)+ch-
'0';ch=getchar();}
return x*f;
}
int T,n;
char s[N];
int num[N],Next[N];
void Get_Num()
{
for(
int i=
1;i<=n;i++) num[i]=
0;
Next[
1]=num[
1]=
1;
for(
int i=
2,j=
1;i<=n;i++)
{
while(j>
1&&s[j]!=s[i]) j=Next[j-
1];
if(s[i]==s[j]) j++;
Next[i]=j;
num[i]=num[j-
1]+
1;
}
int ans=
1;
for(
int i=
2,j=
1;i<=n;i++)
{
while(j>
1&&s[j]!=s[i]) j=Next[j-
1];
if(s[i]==s[j]) j++;
while(((j-
1)<<
1)>i&&j>
1) j=Next[j-
1];
ans=
1LL*ans*(num[j-
1]+
1)%mod;
}
printf(
"%d\n",ans);
}
void Solve()
{
scanf(
"%s",s+
1);
n=
strlen(s+
1);
Get_Num();
}
int main()
{
T=read();
while(T--) Solve();
return 0;
}
