目录

Period (KMP算法 最小循环节 最大重复次数) 题目思路题解

Period (KMP算法 最小循环节 最大重复次数)

题目

给出一个字符串s,问在[0, i]区间是否有完整的循环节,若有,输出i并输出循环次数Input The input file consists of several test cases. Each test case consists of two lines. The first one contains N (2 <= N <= 1 000 000) – the size of the string S. The second line contains the string S. The input file ends with a line, having the number zero on it.Output For each test case, output “Test case #” and the consecutive test case number on a single line; then, for each prefix with length i that has a period K > 1, output the prefix size i and the period K separated by a single space; the prefix sizes must be in increasing order. Print a blank line after each test case.ample Input 3 aaa 12 aabaabaabaab 0Sample Output Test case #1 2 2 3 3

Test case #2 2 2 6 2 9 3 12 4

思路

见 这篇博客 然后枚举就好

题解

#include <iostream> #include <cstring> #define N 1000020 using namespace std; char str[N]; int nex[N]; int len; void getNext() { int i = -1, j = 0; nex[0] = -1; while (j < len) { if (i == -1 || str[i] == str[j]) nex[++j] = ++i; else i = nex[i]; } } int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int k, kase = 1; while (cin >> k) { if(k==0) break; cout << "Test case #" << (kase++) << endl; cin >> str; len = strlen(str); getNext(); for (int i = 2; i <= k; i++) { int son = i - nex[i]; if (i % son == 0 && nex[i] != 0) { cout<<i<<" "<<(i/son)<<endl; } } cout<<endl; } }

转载于:https://www.cnblogs.com/tttfu/p/11309298.html