题解 P3426 【[POI2005]SZA-Template】

2017-10-26 15:23:30


【POI补全计划#10 POI2005 SZA】

鉴于我没看懂kczno1巨神的题解,我决定自己来写一个

看题立刻想到KMP,就先把next数组求出来

接下来发现模板串满足三个条件

1.一定是一个前缀

2.结束位置一定是最后一个字符一直沿着next数组走能到达的点

3.这个模板串在原串中的所有出现位置一定能覆盖整个串

于是我们从小到大枚举满足条件2的结束位置,每次判一下能不能覆盖整个串,然后就TLE了

然后猜到一个性质(貌似挺显然的):

能被更短的前缀完全覆盖的前缀一定不是最短的模板串

这就好办了,只需要每次记录当前能覆盖到什么位置,然后每次枚举覆盖到的位置之后的、满足条件2的结束位置,每次判一下能覆盖到哪就做完了

然而我不会算这个复杂度,只知道跑得飞快

贴代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=500010;
char str[MAXN];
int fail[MAXN];
struct atom
{
    int num;
    atom *next;
}*h[MAXN],pool[MAXN];
int top;
int flag[MAXN],arr[MAXN];
int top2,minn;
int main()
{
    scanf("%s",str+1);
    int len=strlen(str+1),k=0;
    for(int i=2;i<=len;++i)
    {
        while(k!=0&&str[k+1]!=str[i])k=fail[k];
        if(str[k+1]==str[i])++k;
        fail[i]=k;
    }
    for(int i=len;i>=1;--i)
    {
        atom *tmp=&pool[++top];
        tmp->num=i;
        tmp->next=h[fail[i]];
        h[fail[i]]=tmp;
    }
    for(int k=len;k;k=fail[k])
    {
        flag[k]=1;
    }
    for(int i=1;i<=len;++i)
    {
        if(flag[i])
            arr[++top2]=i;
    }
    for(int k=1;k<=top2;++k)
    {
        if(arr[k]<=minn)continue;
        memset(flag,0,sizeof(flag));
        int last=arr[k];
        flag[arr[k]]=1;
        for(int i=arr[k];i<=len;++i)
        {
            if(flag[i])
            {
                for(atom *tmp=h[i];tmp;tmp=tmp->next)
                {
                    flag[tmp->num]=1;
                }
                last=i;
            }
            else if(i-last>=arr[k])break;
        }
        if(last==len)
        {
            printf("%d\n",arr[k]);
            return 0;
        }
        minn=last;
    }
    return 0;
}

update@17.10.26:minor bug fixes