[NOI2014]动物园

题目描述

近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。

某天，园长给动物们讲解KMP算法。

园长：“对于一个字符串

熊猫：“对于字符串

园长：“非常好！那你能举个例子吗？”

熊猫：“例

园长表扬了认真预习的熊猫同学。随后，他详细讲解了如何在

下课前，园长提出了一个问题：“KMP算法只能求出next数组。我现在希望求出一个更强大num数组一一对于字符串

最后，园长给出了奖励条件，第一个做对的同学奖励巧克力一盒。听了这句话，睡了一节课的企鹅立刻就醒过来了！但企鹅并不会做这道题，于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出

特别地，为了避免大量的输出，你不需要输出

输入格式

第

输出格式

包含

输入输出样例

输入 #1

3
aaaaa
ab
abcababc

输出 #1

36
1
32

说明/提示

测试点编号	约定
1
2
3
4
5
6
7
8
9
10

我们将递归用的变量

这时再递归求解，总时间效率是

(附带一句,这动物园的动物都比我NB······)

#include <cstdio>
#include <cstring>
using namespace std;

char s[1000005];

int P[1000005],ch[1000005],n,j,len;

long long ans;

const long long Mod=1e9+7;

int main(){
    int i;
    scanf("%d",&n);
    while(n--){
        scanf("%s",s+1);
        memset(P,0,sizeof(P));
        len=strlen(s+1);
        ans=1;
        j=0;
        P[1]=0;
        ch[1]=1;
        for(i=1;i<len;i++){
            while(j&&s[i+1]!=s[j+1]){
                j=P[j];
            }
            j+=(s[i+1]==s[j+1]);
            P[i+1]=j;
            ch[i+1]=ch[j]+1;
        }
        for(i=1;i<len;i++){
            while(j&&s[i+1]!=s[j+1]){
                j=P[j];
            }
            j+=(s[i+1]==s[j+1]);
            while(j>((i+1)>>1)){
                j=P[j];
            }
            ans=ans*((ch[j]+1)%Mod)%Mod;
        }
        printf("%lld
",ans%Mod);
    }
    return 0;
}