洛谷3426 [POI2005]SZA-Template

Luogu

分析

$\mathrm{KMP+DP}$ 。

先把 $nxt$ 求出来,考虑怎么 $\mathrm{DP}$ 。

设 $f[i]$ 表示前缀 $i$ 的答案。显然 $f[i]$ 只能取 $i$ 或 $nxt[i]$ 。

进一步发现, $f[i]$ 取 $nxt[i]$ 仅当存在一个 $j$ ,满足 $f[j]=f[nxt[i]]$ 且 $i-nxt[i]\leq j$ 。

实际上不用每次循环找 $j$ ,开个桶记一下即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

const int N=500000+10;

char s[N];
int nxt[N],f[N],o[N];

int main() {
    scanf("%s",s+1); int n=strlen(s+1);
    nxt[0]=-1;
    for (re int i=2,j=0;i<=n;++i) {
        while (j!=-1&&s[j+1]!=s[i]) j=nxt[j];
        nxt[i]=++j;
    }
    f[1]=1;
    for (re int i=2;i<=n;++i) {
        if (o[f[nxt[i]]]>=i-nxt[i]) f[i]=f[nxt[i]];
        else f[i]=i;
        o[f[i]]=i;
    }
    printf("%d\n",f[n]);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 36 PM

发表评论