【KMP】重复子串（ybtoj KMP-2）

正题

ybtoj KMP-2

---

题目大意

问你一个字符串最多由多少个相同的字符串组合而成

---

解题思路

如下图，先用KMP求出nx数组，那么有$1\sim n{x}_n$和$(n-n{x}_n)\sim n$相匹配

不难推出$1\sim (n-n{x}_n)$和$n{x}_n\sim n$匹配，则$n{x}_n\sim n$为最小的相同的字符串

如果$(n-n{x}_n)\mid n$那么有解

---

代码

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define ll long long #define N 1000100 using namespace std; int nx[N]; char str[N]; void gnx(char* s) {int n = strlen(s + 1);for (int 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("%s", str + 1);while (str[1] != '.') {gnx(str);int n = strlen(str + 1);nx[1] = 0;if (n % (n - nx[n]) == 0)//判断是否有解printf("%d\n", n / (n - nx[n]));elseputs("1");scanf("%s", str + 1);}return 0; }

总结

以上是生活随笔为你收集整理的【KMP】重复子串（ybtoj KMP-2）的全部内容，希望文章能够帮你解决所遇到的问题。

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