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

你的名字 2023-06-01 06:12 13阅读 0赞

*  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  
0  
**Sample Output**  
Test case \#1  
2 2  
3 3

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

## 思路 ##

见 [这篇博客][Link 1]  
然后枚举就好

## 题解 ##

#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

[Link 1]: https://www.cnblogs.com/tttfu/p/11309093.html