【洛谷-P3426】[POI2005]SZA-Template

题目链接：P3426 [POI2005]SZA-Template - 洛谷 - 计算机科学教育新生态 ↗

设 $\operatorname{dp}[i]$ 表示前缀 $[1, i]$ 的答案，设 $\operatorname{lst}[i]$ 表示以前缀 $[1, i]$ 为印章，最远能覆盖到的位置。

容易发现，前缀 $[1, i]$ 一定能被自己覆盖，因此 $\operatorname{dp}[i]$ 最大为 $i$。

其何时能被更短的段覆盖?

考虑其 $\rm{border}$，我们以覆盖其 $\rm{border}$ 相同的方式，也就是以 $\operatorname{dp}[\operatorname{border}[i]]$ 为印章长度，尝试覆盖 $[1, i]$。

如果可行，那么 $\operatorname{dp}[i]=\operatorname{dp}[\operatorname{border}[i]]$。

判断可行？

可行当且仅当：$\operatorname{lst}[\operatorname{dp}[\operatorname{border}[i]]] >= i - \operatorname{border}[i]$.

意思就是，以 $\operatorname{dp}[\operatorname{border}[i]]$ 为印章长度，至少要可以覆盖到 $i - \operatorname{border}[i]$。

$[i - \operatorname{border}[i], i]$ 这段与 $[1, \operatorname{border}[i]]$ 完全相同，一定能被覆盖，所以只需 $[i-\operatorname{border}[i]]$ 之前能被覆盖。

#include <bits/stdc++.h>
using namespace std;
const int MAXLEN  = 5e5 + 10;
char s[MAXLEN];
int len, nxt[MAXLEN];
void get_border() {
    nxt[1] = 0;
    for(int i = 2; i <= len; i++) {
        int match = nxt[i - 1];
        while(s[i] != s[match + 1] && match != 0) match = nxt[match];
        if(s[i] == s[match + 1]) match++;
        nxt[i] = match;
    }
}
int dp[MAXLEN]; //dp[i]表示前缀[1, i]的答案
int lst[MAXLEN]; //lst[i]表示以前缀[1, i]为印章，最远能覆盖到的位置
int main() {
    scanf("%s", (s + 1)); len = strlen(s + 1);
    get_border();
    dp[1] = 1; lst[1] = 1;
    for(int i = 2; i <= len; i++) {
        dp[i] = i;
        if(lst[dp[nxt[i]]] >= i - nxt[i]) dp[i] = dp[nxt[i]];
        lst[dp[i]] = i;
    }
    cout << dp[len] << endl;
    return 0;
}