poj 1961 Period 【KMP-next前缀数组的应用】

题目地址：http://poj.org/problem?id=1961

Sample 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

题目分析：给你一个字符串，最大长度1百万。输出是：以第1组样例解释，在aaa的字符串中，长度为2时，存在2个循环节a。当长度为3时，存在3个循环节a。
以第二组样例解释，当长度为2时，存在2个循环节a。当长度为6时，存在2个循环节aab。当长度为9时，存在3个循环节aab。依次类推下去。
此题就是poj 2406的难度加强版本。
code:

#include <stdio.h>

#include <string.h>

#include <stdio.h>

char s[1000000+10];

int next[1000000+10];

void get_next(int len)

{

    int i=0, j=-1;

    next[0]=-1;

    while(i!=len)

    {

        if(j==-1 || s[i]==s[j])

            next[++i]=++j;

        else

            j=next[j];

    }

}

int main()

{

    int n;

    int i, j, len;

    int cnt=1;

    while(scanf("%d%*c", &n)!=EOF)

    {

        if(n==0) break;

        scanf("%s", s);

        get_next(n);

        printf("Test case #%d\n", cnt++);

        for(i=1; i<=n; i++){

            len=i-next[i];//计算的循环节的长度

            if(i!=len && i%len==0){

                printf("%d %d\n", i, i/len);

            }

        }

        printf("\n");

    }

    return 0;

}

巴特西

poj 1961 Period 【KMP-next前缀数组的应用】

最新文章

热门文章