HDU 1358

3974 ワード

http://acm.hdu.edu.cn/showproblem.php?pid=1358
ある接頭辞の周期を求めて、Nextで循環節の題目を求めます

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std ;

char B[1000005] ;

int Next[1000005],lenB ;

void GetNext()

{

    int i,j ;

    Next[1]=j=0 ;

    for(i=2 ;i<=lenB ;i++)

    {

        while(j>0 && (B[j+1]!=B[i]))j=Next[j] ;

        if(B[j+1]==B[i])j++ ;

        Next[i]=j ;

    }

}

int main()

{

    int cas=1 ;

    while(scanf("%d",&lenB),lenB)

    { 

        scanf("%s",B+1) ;

        GetNext() ;

        printf("Test case #%d
",cas++) ; for(int i=2 ;i<=lenB ;i++) { if(i%(i-Next[i])==0 && Next[i]) printf("%d %d
",i,i/(i-Next[i])) ; } putchar('
') ; } return 0 ; }

View Code