[KMP]poj 1961:Period
大体の意味: nの長さの文字列を与え、それぞれ前のnビットプレフィックスを求め、それぞれいくつかの同じサブストリングによって接続されてもよい.
大体の考え:
相変わらずnext配列のフレキシブルな運用は、poj 2406と同じです.ここでは詳しく説明しません.
大体の考え:
相変わらずnext配列のフレキシブルな運用は、poj 2406と同じです.ここでは詳しく説明しません.
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=1000005;
char pat[nMax];
int lenp,next[nMax];
void get_next(){
int i,j=-1;
next[0]=-1;
for(i=1;i<=lenp;i++){
while(j>-1&&pat[j+1]!=pat[i])j=next[j];
if(pat[j+1]==pat[i])j++;
next[i]=j;
}
}
int main(){
int cas=0;
while(scanf("%d",&lenp)!=EOF&&lenp){
cas++;
scanf("%s",pat);
printf("Test case #%d
",cas);
get_next();
for(int i=2;i<=lenp;i++){
int l=(i-1)-next[i-1];
if(i%l==0&&i!=l){
cout<<i<<" "<<i/l<<endl;;
}
}
printf("
");
}
return 0;
}