周期 (period)

基本概念

文字列 \(w\) に対し，整数 \(p \in \{1, \dots, |w| \}\) が \(w\) の 周期 (period) であるとは， すべての \(1 \leq i \leq |w|-p\) に対して \(w[i] = w[i+p]\) が成立するときをいう．

注釈

例えば，5と7と8は文字列 \(abaababa\) の周期である．

文字列 \(w\) に対し， \(|w|\) は \(w\) の周期であるので，周期は常に定義できている． 文字列 \(w\) の周期の中で最も小さいものを \(w\) の 最小周期 といい， \(period(w)\) と表す．

注釈

例えば， \(period(abaababa) = 5\) ．

w =

・length(w) = dummy

・period(w) = dummy

周期は， 境界 (border) と表裏の関係にある．

アルゴリズム

入力として与えられた文字列の最小周期を計算するアルゴリズム

• 素朴なもの

      var n = w.length;
      if ( n == 0 ) {
	return 0;
      }	       
      for( var p=1; p <= n; p++ ) {
        var flag = true;
        for(var i=0; i < n-p; i++ ){
          if ( w[i] != w[i+p] ) {
            flag = false;
            break;
          }
        }
        if ( flag == true ) {
          return p;
        }
      }
    };
    

• pythonに変換

  /Scripts/Python/period.py

参考文献