KMP-[POI2005]SZA-Template-解题报告

· · 题解

发这篇题解完全是因为题解里的方法都好麻烦啊...好像是我们暑假考试的题

我们肯定是要KMP求出next数组（以下可能简称nx），然后想办法DP。

我们直接设f[i]表示前缀i的答案。

然后我们考虑，f[i]只有2种取值：i,f[nx[i]]，原因很简单，想覆盖i起码要覆盖nx[i]。

什么时候答案才能为f[nx[i]]呢，因为前缀i的最后几个字符为nx[i]，所以我们最多在后面接上nx[i]这么长的字符串，也就是充要条件为存在一个j，使得f[j]=f[nx[i]],i-nx[i]\le j

具体实现的话开一个桶即可。

#define N 500005
int n;
int nx[N];
int f[N],h[N];
char s[N];
signed main()
{
#ifdef M207
    freopen("in.in","r",stdin);
    // freopen("out.out","w",stdout);
#endif
    scanf("%s",s+1); n=strlen(s+1);
    nx[0]=-1;
    for(ri i=2,j=0; i<=n; ++i)
    {
        while(j!=-1&&s[j+1]!=s[i]) j=nx[j];
        nx[i]=++j;
    }
    f[1]=1;
    for(ri i=2; i<=n; ++i)
    {
        f[i]=i;
        if(h[f[nx[i]]]>=i-nx[i]) f[i]=f[nx[i]];
        h[f[i]]=i;
    }
    out(f[n]);
    return 0;
}