aaa
今天字符串专题
1） KMP
思想是对于每一位求出最长的后缀等于前缀的长度 next
周期：
字符串：【】【】【】【】【不完整周期】
【】就是周期
有一个周期就是串长减去 next，
所有周期长度都是最小周期的倍数；
如果串不是最小周期的倍数，则这个串没
有循环节。
【NOI2014 动物园】
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll M=1e9+7;
ll n;
ll num[N];
ll kmp[N];
ll Ans(string str){
ll len=str.size();
ll ans=1;
ll j=0;
num[1]=1;
for(ll i=1;i<len;i++){
while(j&&(str[j]!=str[i])){
j=kmp[j];
}
if(str[j]==str[i]) j++;
kmp[i+1]=j;
num[i+1]=num[j]+1;
}
j=0;
for(ll i=1;i<len;i++){
while(j&&(str[j]!=str[i])){
j=kmp[j];
}
if(str[j]==str[i]) j++;
while(j>(i+1)/2) j=kmp[j];
ans=(ans*(num[j]+1))%M;;
}
return ans;
}
int main(){
cin>>n;
while(n--){
string str;
cin>>str;
memset(kmp,0,sizeof(kmp));
//memset(num,0,sizeof(num));
cout<<Ans(str)<<endl;
}
return 0;
}