题目链接: HDU1358

题目大意: 给一段长度为n的字符串，让你求出长度为s的完美前缀字串(含k段循环节)的字串长度len以及循环次数k，k取最大(即循环节长度取最小)

解题思路: 关于next数组性质的应用

/**
 * HDU_1358
 *
 * 输入: n以及长度为n的串。0表示输入结束
 * 输出：循环节的长度以及循环的周期（循环周期取最大）
 *
 */

/**
 *
 * next数组:
 * 当i = 0时，next[0] = -1
 * 当i > 0时, next[i] = k 表示对于到达长度为i的字符串pattern的最长相等前后缀的长度
 * ---------------------------------------------------------------------------------------
 * 也可以这么理解：
 * 设在字符串S中查找模式串T，若S[m]!=T[n],那么，取T[n]的模式函数值next[n],
 * 1.next[n]=  -1 表示S[m]和T[0]间接比较过了，不相等，下一次比较 S[m+1] 和T[0]
 * 2.next[n]=0 表示比较过程中产生了不相等，下一次比较 S[m] 和T[0]。
 * 3.next[n]= k >0 但k<n, 表示,S[m]的前k个字符与T中的开始k个字符已经间接比较相等了，下一次比较S[m]和T[k]相等吗？
 * 4.其他值，不可能。
 * 原文：https://blog.csdn.net/whyorwhnt/article/details/8883074
 * ----------------------------------------------------------------------------------------
 *
 */

 /**
 *
 * next数组的性质:
 * 如果len%（len-next[len]）==0，则字符串中必存在最小循环节，且循环次数即为len/（len-next[len]）;
 *
 */
#include <stdio.h>
#include <iostream>
using namespace std;

const int maxn = 1000010;
int N;
char Tmp[maxn];
int prefix[maxn];

void get_prefix_table (int n) {
    int i = 0, len = -1;
    prefix[0] = -1;
    while (i < n) {
        if(len == -1 || Tmp[i] == Tmp[len]) {  //考虑前缀长度为n的数组作为前缀表
            len++;
            i++;
            prefix[i] = len;
        }else {
            len = prefix[len];
        }
    }
}

int main() {
    int cnt = 0;
    while (~scanf("%d",&N) && N != 0) {
        scanf("%s",Tmp);
        get_prefix_table(N);
        printf("Test case #%d\n",++cnt);
        for (int i = 1; i <= N; i++) { //长度为i的串
            if(prefix[i] > 0) { //当前前后缀相同的个数>0时才有讨论
                int j = i - prefix[i];
                if(i % j == 0) {
                    printf("%d %d\n",i,i/j);
                }
            }
        }
        printf("\n");
    }

    return 0;
}