HDU – 1358 Period

Period

KMP算法和周期性字符串.

i-next[i] 为最小循环元长度,i/(i-next[i])为最大循环次数.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;

int Next[1000010];
char p[1000010];

void kmp_pre(char x[],int m,int next[]){
    int i,j;
    j=next[0]=-1;
    i=0;
    while(i<m){
      while(-1!=j&&x[i]!=x[j]) j=next[j];
      next[++i]=++j;
    }
}

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int kase=0;
  int n;
  while(cin>>n&&n){
    scanf("%s",p);
    kmp_pre(p,n,Next);
    int i=n;
    printf("Test case #%d\n",++kase);
    for(int i=2;i<=n;++i){
        if(i/(i-Next[i])>1&&i%(i-Next[i])==0){
            printf("%d %d\n",i,i/(i-Next[i]));
        }
    }
    printf("\n");
  }

  return 0;
}