NOI2014 动物园
题目简要描述
设num[i]表示既是S[1..i]的前缀又是后缀,并且前缀和后缀不重叠的字符串个数。
求\(\prod_{i=1}^n (num[i]+1)=(num[1]+1)\times
(num[2]+1)\times \dots \times (num[n]+1)\)对\(1000000007\)取模的结果。 10%:|S|<=50
30%:|S|<=200 50%:|S|<=10000 100%:|S|<=1000000 ###
一些定义 设fail2[i]表示最长的符合要求的字符串长度。
设sum[i]表示既是S[1..i]的前缀又是后缀的字符串个数。(可以和S[1..i]相同)。
设fail[i]表示最长的既是S[1..i]的前缀又是后缀的并且和S[1..i]不同的字符串长度,
则sum[i]=sum[fail[i]]+1。 我们发现num[i]=sum[fail2[i]] ### (大)暴力
求fail2[i]的时候根据fail指针搜。 并不知道能否获得50分。 ###
正解水过去的方法 求fail2[i]的时候用倍增。可以水到100分。 ###
正解 fail2和fail有着相同的性质:fail2[i]<=fail2[i-1]+1(显然)
那么直接像KMP一样就好了。 代码如下:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define up(a,b,c) for (long long a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (long long a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (long long a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (long long a(b),end##a(c);a>=end##a;--a)
using namespace std;
long long read(){
char s;
long long k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9'){
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
void write(long long x){
if(x<0){
putchar('-');
write(-x);
}
else{
if(x/10)write(x/10);
putchar(x%10+'0');
}
}
char s[2333333];
long long f[2333333],f2[2333333],num[2333333],num2[2333333];
//f[i]-->fail[i] f2[i]-->fail2[i] num[i]-->sum[i] num2[i]-->num[i]
int main(){
long long n,t,l,ln,ans;
scanf("%lld\n",&n);//多组数据
while(n){
--n;
scanf("%s\n",s+1);
ln=strlen(s+1);
t=0,l=0;ans=1;
num[1]=1;
for(int i=2;i<=ln;++i){
f[i]=f2[i]=num[i]=num2[i]=0;
while(s[t+1]!=s[i]&&t)t=f[t];
while((s[l+1]!=s[i]&&l)||i/2<=l)l=f[l];
if(s[t+1]==s[i])f[i]=++t;//47和49行是标准的KMP算法
if(s[l+1]==s[i])f2[i]=++l;
num[i]=num[f[i]]+1;
num2[i]=f2[i]?num[f2[i]]?num[f2[i]]:1:0;
ans*=num2[i]+1;
ans%=1000000007;
}
//up(i,2,ln)printf("%d %d %d %d\n",f[i],f2[i],num[i],num2[i]);
printf("%lld\n",ans);
}
return 0;
}