Loading... [Link](https://www.luogu.com.cn/problem/P3426) ## 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 ```cpp #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 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏