首页
登录 | 注册

[KMP]UOJ#5. 【NOI2014】动物园 题解

题目大意

多组数据,每次给出一个长度为n的字符串,求它的i=1n(num[i]+1) Mod 1000000007

num[i]的定义为:对于字符串长度为i的前缀子串中,前缀等于后缀且前缀与后缀不重叠的子串个数。

解题报告

这题讲了一大堆KMP,所以解法肯定也与KMP有关,不重叠就是要求匹配子串长度不能超过原串一半,如果把这个条件去掉,num[i]就是问指针要在nxt数组上跳多少次才能跳到0。假设我们处理第i位,一路匹配最终匹配到第j位,如果从第j位跳到0需要num[j],那么明显num[i]=num[j]+1,一波递推出结果,现在要求不能重叠,所以不能直接*num[i],先跳到一个没有重叠的子串,然后更新答案。

示例代码

UOJ BZOJ LibreOJ ……

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000005,tt=1000000007;
int tst,n,nxt[maxn],num[maxn];
char a[1000005];
long long ans;
int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d",&tst);
    while (tst--){
        scanf("%s",a+1); n=strlen(a+1);
        nxt[1]=0; ans=num[1]=1;
        for (int i=2,j=0;i<=n;i++){
            while (j&&a[j+1]!=a[i]) j=nxt[j];
            if (a[j+1]==a[i]) j++;
            nxt[i]=j; num[i]=num[j]+1;
        }
        for (int i=2,j=0;i<=n;i++){
            while (j&&a[j+1]!=a[i]) j=nxt[j];
            if (a[j+1]==a[i]) j++;
            while ((j<<1)>i&&j) j=nxt[j];
            ans=ans*(num[j]+1)%tt;
        }
        printf("%lld\n",ans);
    }
    return 0;
}


2020 jeepshoe.net webmaster#jeepshoe.net
12 q. 0.351 s.
京ICP备10005923号