题解 P3426 【[POI2005]SZA-Template】

kczno1 · 2017-06-12 15:55:43 · 题解

考虑一个前缀i可以涂完意味着什么。

首先，他得是n的border。

并且，如果把所有border为它的点列出来，相邻差的max<=i。

对应到kmp的next构成的树上,

就是i在n到根的那条链上，并且把他子树的点列出来，相邻差的max<=i。

从根往n那边走，在删点的同时维护每个点的前驱后继，从而维护max，就可以了。

#include<bits/stdc++.h>
using std::vector;

#define rep(i,l,r) for(int i=l;i<=r;++i)
#define pb push_back
void chmax(int &x,int y)
{
    if(x<y)x=y;
}
const int N=5e5+5;
char s[N];int n,next[N];
int to[N];
vector<int>son[N];

int pre[N],suf[N],mx;

void del(int x)
{
    if(x)
    {
        int p=pre[x],s=suf[x];
        chmax(mx,s-p);
        suf[p]=s;pre[s]=p;
    }
    for(vector<int>::iterator i=son[x].begin();i!=son[x].end();++i)
    if(*i!=to[x]) del(*i);
}

int main()
{
    freopen("1.in","r",stdin);
    scanf("%s",s+1);
    n=strlen(s+1);
    int j=0;
    rep(i,2,n)
    {
        while(j&&s[j+1]!=s[i])j=next[j];
        if(s[j+1]==s[i]) next[i]=++j;
    }

    rep(i,1,n)son[next[i]].pb(i);
    for(int i=n;i;i=next[i]) to[next[i]]=i;

    rep(i,1,n) {pre[i]=i-1;suf[i]=i+1;}
    del(0);
    int i=1;
    while(mx>i) { del(i);i=to[i]; }
    printf("%d\n",i);
}