PKU : 1961 - Period

問題概要

文字列Sが与えられます.
Sの接頭辞全てについて, 最大で何回同じ文字列が繰り返されているか答える問題です.
ただし, 1回しか繰り返されない場合は出力してはいけません.

例) abaababaab

• 6 2 : 6文字目までで, abaが2回繰り返された
• 10 2 : 10文字目までで, abaabが2回繰り返された

アルゴリズム

KMP法のアルゴリズムを応用する問題でした.

• KMP法について

上記のページにおける, パターン照合テーブルを作成すれば, そこから答えを導くことができます.

っていうのを, Webで調べました（ｺｿｯ

プログラム

コメントは, 僕用に適当な推測で書いてるので, 信用しないでください.
そもそも, 理解できないと思います.

int next[1000010];
char s[1000010];

int main(){
  int n;

  for(int SET=1;scanf("%d",&n) && n!=0;SET++){
    printf("Test case #%d\n",SET);
    scanf("%s",s);

    int i = 0; //現在の文字数
    int j = -1; //比較位置のインデックス
    next[0] = -1;

    while(i < n){
      if(j == -1 || s[i] == s[j]){
        i++;
        j++;
        next[i] = j; //これで, iの文字が一致しないときの比較位置は, jに戻すだけでよくなる

        int len = i - next[i]; //KMPテーブルから, 繰り返し文字列の長さを求める
        if(i % len == 0 && i / len > 1){ //繰り返しが2回以上ならば出力
          printf("%d %d\n",i,i/len);
        }
      }
      else{
        j = next[j]; //比較位置を戻す
      }
    }

    printf("\n");
  }
}