.. -*- coding: utf-8; -*-

==================================================
周期 (period)
==================================================

基本概念
~~~~~~~~~~~~~~~~~~~~

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

.. note::
   
  例えば，5と7と8は文字列 :math:`abaababa` の周期である．

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

.. note::

  例えば， :math:`period(abaababa) = 5` ．

.. raw:: html
         
   　　　<script type="text/javascript"  src="../../_static/basicAlgorithms.js">
         </script>

          <form onsubmit="return false;" autocomplete="off">
          <div>
          w = <input id="w" type="text" size="64" value="abaababa"/>
          </div>
          </form>
          <div> ・length(w) = <wlength>dummy</wlength> </div>
          <div> ・period(w) = <wperiod>dummy</wperiod> </div>

  
周期は， :doc:`border` と表裏の関係にある．

.. 
	todo::
   周期との関係を例を使いながらもっと詳しく書く．


   
アルゴリズム
======================

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


- 素朴なもの

..	（実際に上記の対話型フォームにはこのプログラムが使われているが，もっと美しく誰か書き直して下さい）

.. literalinclude:: /_static/basicAlgorithms.js
   :language: javascript
   :lines: 11-28
   :linenos:

   
- pythonに変換
   :download:`/Scripts/Python/period.py`

.. literalinclude:: /Scripts/Python/period.py
   :pyobject: period

      
.. - 線形時間のもの（誰かお願い）


参考文献
==================

.. 
	* XXXXX


   
.. 
	note::
	上記の説明では文字列の添え字を 1-オリジンで書いているが，
	実際に使われているプログラムの中では 0-オリジンになっているため
	ちょっとわかりにくい．なんとかならないものか．

.. 
	todo::
	pythonプログラムの場合には，コードサンプルで pyobject:period のような指定の仕方でプログラム中の
	該当する関数部分だけを抜き出してきて表示できる．
	Javascript でのやり方が，まだよくわからないのでここでは行番号を指定しているが，プログラムを
	書き直す度に修正するのは大変なので，そのうち調べておきたい．