【kmp算法next数组-串的最小循环节/循环周期】Period HDU

【kmp算法next数组-串的最小循环节/循环周期】Period HDU - 1358

Think:
1知识点：通过kmp算法的next数组求解串的最小循环节和循环周期
2题意：一个长为N (2 <= N <= 1 000 000) 的字符串，询问前缀串长度为k(k > 1)的串是否是一个周期串，即k = A…A;若是则按k从小到大的顺序输出k和周期数
3解题知识点：
（1）：一个串的最小循环节长度：len - next[len]
（2）：若len%(len-next[len]) == 0, 则这个字符串的最小周期为len/(len-next[len])

vjudge题目链接

建议参考博客—参考博主题意

以下为Presentation Error代码—题目要求每组测试数据之后需要输出空行

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int size_P = 1000414;
int _next[size_P];
char st1[size_P];
void get_next(char *P, int len_P);
int main(){
    int k = 1;
    int n, i, cir_len;
    while(~scanf("%d", &n) && n){
        scanf("%s", st1);
        get_next(st1, n);
        printf("Test case #%d\n", k++);
        for(i = 1; i <= n; i++){
            cir_len = i - _next[i-1];
            if(cir_len != i && i%cir_len == 0)
                printf("%d %d\n", i, i/cir_len);
        }
    }
    return 0;
}
void get_next(char *P, int len_P){
    int q, k;
    _next[0] = 0;
    k = 0;
    for(q = 1; q < len_P; q++){
        while(k > 0 && P[k] != P[q]){
            k = _next[k-1];
        }
        if(P[k] == P[q])
            k++;
        _next[q] = k;
    }
}

以下为Accepted代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int size_P = 1000414;
int _next[size_P];
char st1[size_P];
void get_next(char *P, int len_P);
int main(){
    int k = 1;
    int n, i, cir_len;
    while(~scanf("%d", &n) && n){
        scanf("%s", st1);
        get_next(st1, n);
        printf("Test case #%d\n", k++);
        for(i = 1; i <= n; i++){
            cir_len = i - _next[i-1];
            if(cir_len != i && i%cir_len == 0)
                printf("%d %d\n", i, i/cir_len);
        }
        printf("\n");
    }
    return 0;
}
void get_next(char *P, int len_P){
    int q, k;
    _next[0] = 0;
    k = 0;
    for(q = 1; q < len_P; q++){
        while(k > 0 && P[k] != P[q]){
            k = _next[k-1];
        }
        if(P[k] == P[q])
            k++;
        _next[q] = k;
    }
}