Loading... [Link](https://www.luogu.com.cn/problem/P3435) ## Sol 考察 KMP 算法中 `nxt` 的一个重要性质:一个串的循环节长度为 $|S| - nxt_{|S|}, |S| - nxt_{nxt_{|S|}} \dots$ 现在要求给定字符串所有前缀的最大周期长度之和。 那么就是要最小化每一个 $nxt_{|S|}, nxt_{nxt_{|S|}}, \dots$ 做完了 那么怎么来理解这件事情,你最开始知道 `nxt` 用来每次失配的时候跳一段跟前缀(可能已经跟文本串匹配了一段 $\geq 0$ 的长度),这样每次就可以减少重复的比较。那么 $|S| - nxt_{|S|}$ 相当于往 $|S|$ 一段跟后缀相等的前缀跳。那么那个前缀起始位置之前应该又有一段跟这一样的跳法跳出来的相等的真前后缀。(可能有点绕,但是结合 `nxt` 的实际意义多理解就会明白) ## Code ```cpp #include <bits/stdc++.h> using namespace std; typedef long long LL; const int SIZE = 1e6 + 5; const LL inf = 1e18; int n; int nxt[SIZE], f[SIZE]; char str[SIZE]; int main() { // freopen("code.in", "r", stdin); scanf("%d", &n); scanf("%s", str + 1); LL ans = 0; for (int i = 2, j = 0; i <= n; ++ i) { for ( ; j && str[i] != str[j + 1]; j = nxt[j]); if (str[j + 1] == str[i]) ++ j; nxt[i] = j; if (!f[j]) f[i] = j; else f[i] = f[j]; if (f[i]) ans += 1ll * (i - f[i]); } printf("%lld\n", ans); return 0; } ``` 最后修改:2021 年 09 月 07 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏