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;
}