Link

Sol

性质证明大题

设表示前缀为 $i$ 的模板长度的最小值。

性质有两:

  1. $f_i = nxt_i$ 或 $f_i = i(nxt_i < i)$
  2. $f_i = f_{nxt_i} \Leftrightarrow \exists j \in [i - nxt_i, i], f_j = f_{nxt_{i}}$

第一个这个 $f_{nxt_i}$ 你可以理解为拼出了 $nxt_i$ 后,可以把 $nxt_i$ 当成一个整体,我们可以用 $nxt$ 这个整体拼出 $i$

第二个如果 $\exists j \in [i-nxt_i, i]$ 满足 $f_j = f_{nxt_{i}}$,那么一定可以拼一个 $nxt_i$ 构成 $i$。

画图吧同志们

Code

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

const int SIZE = 5e5 + 5;

int pos[SIZE], nxt[SIZE], f[SIZE];
char str[SIZE];

int main() {
    // freopen("code.in", "r", stdin);
    scanf("%s", str + 1); int n = (int) strlen(str + 1);
    for (int i = 2, j = 0; i <= n; ++ i) {
        for ( ; j && str[j + 1] != str[i]; j = nxt[j]);
        if (str[j + 1] == str[i]) ++ j;
        nxt[i] = j;
    }
    for (int i = 1; i <= n; ++ i) {
        f[i] = i;
        if (pos[f[nxt[i]]] >= i - nxt[i]) f[i] = f[nxt[i]];
        pos[f[i]] = i;
    }
    printf("%d\n", f[n]);
    return 0;
}
最后修改:2021 年 09 月 07 日
如果觉得我的文章对你有用,请随意赞赏