KMP!!!!骗子!!!!!骗子!!!!骗子!!!!!!
这道题被放进后缀数组题单里面。但是用后缀数组的方***超时。t到死。。。。。。。。。骗子!
后缀数组思路:
我们要求最小的循环子串。利用后缀数组:
如果 a1 a2 a3 a4 a5 a6 a7 a8 a9 的最小循环子串长为3即以a1 a2 a3为循环的话。
我们就可以发现 a4为起始的后缀应该和a1为起始的后缀的最大公共前缀和为6.即为a4的长度!!!!
这里是必须使a4的长度的。
那么我们就可以求出高度数组,利用st表。枚举s长度的因数,利用st表枚举长度。
但这会t!!!
正确的思路为KMP。我们再回到上面的例子:
a1 a2 a3 a4 a5 a6 a7 a8 a9
KMP的next数组求得其实就是求最长的相同前缀和后缀。(其实我个人觉得有点dp的感觉)
那我们看上面的例子,不就是求a9处的最大相同前缀后缀吗!!
a9求出的最大相同前缀后缀的长度为6.所以答案就是9/(9-6)=3
如果,最大相同前缀后缀长度被总长度减后不满足因数呢?
那么,答案就应该是1,没有循环子串。
因为首先一点,如果是因数的话一定有循环子串。
如果在有循环字串的基础上最长公共前后缀后还能更长,比如到a2。 而a1 a2 a3是循环字串
那么,我们可以断定a1==a2==a3==a4==.....a9 最小循环字串就变成a1了。矛盾。
所以,如果能整除就存在最小字串。如果不能,就不存在。为1
kmp代码如下:
#include<iostream> #include<algorithm> #include<cstring> using namespace std; const int max_n = 1e6 + 100; char s[max_n]; int net[max_n]; void get_next(char* p,int n) { for (int i = 0, j = -1;i < n;) { if (j == -1 || p[i] == p[j]) net[i++] = j++; else { if (j == 0)j = -1; else j = net[j - 1] + 1; } } } int main() { ios::sync_with_stdio(0); while (cin >> s) { if (s[0] == '.')break; int n = strlen(s); get_next(s, n); if (net[n - 1] == -1)cout << 1 << endl; else { int len = n - 1 - net[n - 1]; if (n % len == 0)cout << n / len << endl; else cout << 1 << endl; } } }