目录

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

思路

见

然后枚举就好

题解

#include 
    
     #include 
     
      #define N 1000020using 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/son)<