「LOJ 2246」「NOI2014」动物园

发表于

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

下课前，园长提出了一个问题： KMP 算法只能求出 nextnext 数组。我现在希望求出一个更强大 numnum 数组——对于字符串 SS 的前 ii 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 numinum_i 。

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

Constraints

nleq5nleq 5 ， L≤106L\leq 10^6

Solution

即是后缀又是前缀的性质与 KMP 算法的 fail 数组很接近，在处理时顺便记录答案即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e6+5;
const int mod=1e9+7;
int T,n,ans,j,fail[N],num[N];
char s[N];
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main()
{
    T=read();
    while(T--)
    {
        scanf("%s",s+1);
        n=strlen(s+1);ans=1;
        num[1]=1;j=0;
        for(int i=2;i<=n;i++)
        {
            while(j&&s[j+1]!=s[i])j=fail[j];
            if(s[j+1]==s[i])j++;
            fail[i]=j;num[i]=num[j]+1;
        }
        j=0;
        for(int i=1;i<=n;i++)
        {
            while(j&&s[j+1]!=s[i])j=fail[j];
            if(s[j+1]==s[i])j++;
            while(j*2>i)j=fail[j];
            ans=1ll*ans*(num[j]+1)%mod;
        }
        printf("%d\n",ans);
    }
    return 0;
}