【KMP】周期长度和（luogu 3435/ybtoj KMP-3）

正题

luogu 3435
ybtoj KMP-3

---

题目大意

定义S的proper前缀为S中非空且len<|S|的前缀，若Q是A的proper前缀，且A是QQ的前缀

现在问你字符串S所有前缀的最大周期之和

---

解题思路

如上图，对于一个字符串S，如果有周期Q，那么蓝色的一段是相同的，此时这段蓝色的是S的公共前后缀

不难发现，对于一段公共前后缀G，S-G即为S的一段周期（减后面的G），要求最大周期，则要使G最小

那么可以用KMP求出nx数组，然后往前跳，跳到0的上一个位置，这个过程和并查集相类似，也可以用到路径压缩

---

代码

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long #define N 1000100 using namespace std; ll n, x, ans, nx[N]; char s[N]; ll find(ll x) { return nx[x] ? nx[x] = find(nx[x]) : x; } void get_nx(char* s, ll n) {nx[1] = 0;for (ll i = 2, j = 0; i <= n; ++i) {while (s[i] != s[j + 1] && j) j = nx[j];if (s[i] == s[j + 1])j++;nx[i] = j;}return; } int main() {scanf("%lld%s", &n, s + 1);get_nx(s, n);for (ll i = 2; i <= n; ++i) ans += i - find(i);//加上剩下部分printf("%lld", ans);return 0; }

总结

以上是生活随笔为你收集整理的【KMP】周期长度和（luogu 3435/ybtoj KMP-3）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。