[BZOJ3670/Luogu2375][Noi2014]动物园(KMP)

发布于 2018-02-21  68 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3670/Luogu2375][Noi2014]动物园(KMP)

Description

近日,园长发现动物园中好吃懒做的动物越来越多了。例如企鹅,只会卖萌向游客要吃的。为了整治动物园的不良风气,让动物们凭自己的真才实学向游客要吃的,园长决定开设算法班,让动物们学习算法。
某天,园长给动物们讲解KMP算法。
园长:“对于一个字符串S,它的长度为L。我们可以在O(L)的时间内,求出一个名为next的数组。有谁预习了next数组的含义吗?”
熊猫:“对于字符串S的前i个字符构成的子串,既是它的后缀又是它的前缀的字符串中(它本身除外),最长的长度记作next[i]。”
园长:“非常好!那你能举个例子吗?”
熊猫:“例S为abcababc,则next[5]=2。因为S的前5个字符为abcab,ab既是它的后缀又是它的前缀,并且找不到一个更长的字符串满足这个性质。同理,还可得出next[1] = next[2] = next[3] = 0,next[4] = next[6] = 1,next[7] = 2,next[8] = 3。”
园长表扬了认真预习的熊猫同学。随后,他详细讲解了如何在O(L)的时间内求出next数组。
下课前,园长提出了一个问题:“KMP算法只能求出next数组。我现在希望求出一个更强大num数组一一对于字符串S的前i个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作num[i]。例如S为aaaaa,则num[4] = 2。这是因为S的前4个字符为aaaa,其中a和aa都满足性质‘既是后缀又是前缀’,同时保证这个后缀与这个前缀不重叠。而aaa虽然满足性质‘既是后缀又是前缀’,但遗憾的是这个后缀与这个前缀重叠了,所以不能计算在内。同理,num[1] = 0,num[2] = num[3] = 1,num[5] = 2。”
最后,园长给出了奖励条件,第一个做对的同学奖励巧克力一盒。听了这句话,睡了一节课的企鹅立刻就醒过来了!但企鹅并不会做这道题,于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出num数组呢?
特别地,为了避免大量的输出,你不需要输出num[i]分别是多少,你只需要输出所有num[i]的乘积,对1,000,000,007取模的结果即可。

Http

BZOJ
Luogu

Tag

KMP

题目大意

给定一个字符串,求每一个前缀中不重叠的相同前后缀个数。

解决思路

考虑一个暴力一点的算法,\(KMP\)求出\(Next\)数组后,对于每一个位置我们都暴力地跳\(Next\)遍历它包含的所有前缀,而这些前缀中长度小于当前位置的二分之一的就是要统计进\(Num\)的。
优化一下,对于每一个位置,我们再记录一个\(Cnt[i]\)表示它包含的前缀个数(包括它自己),那么我们再跳的时候一旦跳到一个长度小于当前前缀长度/2的就停止,直接从这个地方累加\(Cnt\)过来。
再优化一下,前面跳的过程可以用倍增来实现,这样,复杂度就降到\(O(nlogn)\),大力卡常是可以过的。
当然这样的算法不够优美。我们考虑我们把复杂度浪费在了哪里呢?没错,就是每次倍增的复杂度。每一次都倍增求一次位置很耗时间,所以我们考虑用\(pos\)记录上一次找到的合法位置,设当前需要计算的位是\(i\),类似\(KMP\)中移动\(j\)指针寻找与\(str[i]\)匹配的\(str[j+1]\),我们跳\(pos\)指针找到第一个与\(str[i]\)匹配的\(str[pos+1]\),在找到之后,再判断\(2*pos\)是不是小于\(i\),如果不小于,则还要跳\(Next[pos]\)直到满足小于关系。
这样,寻找合法位置的复杂度就与\(KMP\)同阶了。

代码

倍增算法,最慢\(0.9s+\)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define RG register

const int maxN=1000010;
const int Mod=1e9+7;
const int maxBit=20;
const int inf=2147483647;

int n;
char str[maxN];
int Next[maxBit+1][maxN],Size[maxBit+1][maxN];//Next是原KMP中Next的跳转,Size记录跳转中实际经过了几个点
int Num[maxN],Tot[maxN];

int main()
{
    ios::sync_with_stdio(false);
    RG int T;cin>>T;
    while (T--)
    {
        cin>>(str+1);n=strlen(str+1);
        mem(Next[0],0);mem(Size[0],0);
        Next[0][0]=-1;Next[0][1]=0;
        for (RG int i=2;i<=n;++i)//构造Next
        {
            RG int j=Next[0][i-1];
            while ((j!=0)&&(str[j+1]!=str[i])) j=Next[0][j];
            if (str[j+1]==str[i]) Next[0][i]=j+1;
            else Next[0][i]=0;
            Size[0][i]=1;
        }
        //初始化倍增
        for (RG int i=1;i<=maxBit;++i)
            for (RG int j=1;j<=n;++j)
                Next[i][j]=Next[i-1][Next[i-1][j]],Size[i][j]=Size[i-1][j]+Size[i-1][Next[i-1][j]];
        mem(Num,0);mem(Tot,0);Num[0]=-1;
        for (RG int i=1;i<=n;++i)//求解Num
        {
            RG int now=i;//倍增求出i对应的合法位置
            for (RG int j=maxBit;j>=0;--j) if (Next[j][now]*2>i) now=Next[j][now],Tot[i]=Tot[i]+Size[j][now];
            now=Next[0][now];
            Tot[i]+=Tot[now]+1;//Tot记录前缀i包含多少个前缀
            Num[i]=Tot[now];
        }
        RG ll Ans=1;
        for (RG int i=1;i<=n;++i) Ans=Ans*(ll)(Num[i]+1)%Mod;
        printf("%lld\n",Ans);
    }
    return 0;
}

类\(KMP\)的\(pos\)跳转,最慢\(0.040s\)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
#define RG register

const int maxN=1000100;
const int Mod=1e9+7;
const int inf=2147483647;

int n;
char str[maxN];
int Next[maxN];
int Cnt[maxN];

int main()
{
    ios::sync_with_stdio(false);
    RG int T;cin>>T;
    while (T--)
    {
        cin>>(str+1);n=strlen(str+1);
        Cnt[1]=1;
        RG int pos=0;
        RG ll Ans=1;
        for (RG int i=2;i<=n;i++)//求解Next的同时跳转pos
        {
            RG int j=Next[i-1];
            while ((j!=0)&&(str[j+1]!=str[i])) j=Next[j];
            if (str[j+1]==str[i]) Next[i]=j+1;
            else Next[i]=0;
            Cnt[i]=Cnt[Next[i]]+1;//Cnt记录前缀i包含多少个前缀
            while ((pos!=0)&&(str[pos+1]!=str[i])) pos=Next[pos];
            if (str[pos+1]==str[i]) pos++;//将pos跳转到一个匹配的位置
            while (pos*2>i) pos=Next[pos];//再跳转到一个合法的位置
            Ans=Ans*(ll)(Cnt[pos]+1)%Mod;
        }
        printf("%lld\n",Ans);
    }
    return 0;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3670/Luogu2375][Noi2014]动物园(KMP)


HNCJ OIer 一枚