HDU 1358
3974 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=1358
ある接頭辞の周期を求めて、Nextで循環節の題目を求めます
View Code
ある接頭辞の周期を求めて、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