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

===============
 境界 (border)
===============

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

文字列 :math:`w` に対し， :math:`w` の接頭辞でもあり接尾辞でもある文字列を :math:`w` の **境界** *(border)* という．
:math:`w` 自身と，空語 :math:`\varepsilon` は常に :math:`w` の境界である．

:math:`w` の自明でない（つまり :math:`w` 自身ではない）最長の境界を :math:`Border(w)` と表す．

.. note::
   例えば， :math:`Border(abaababa) = aba` である．

境界は， :doc:`period` と表裏の関係にある．

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


アルゴリズム
======================
   
入力として与えられた文字列の境界配列 (border array)を求める問題

文字列 :math:`w` に対し， :math:`border[i] = Border(w[:i])` で定義される配列 :math:`border` を考える．


.. note::
   文字列 abaababa に対する境界配列
   
   ======= == == == == == == == == ==
   i       0  1  2  3  4  5  6  7  8
   ======= == == == == == == == == ==
   文字    　 a  b  a  a  b  a  b  a
   ------- -- -- -- -- -- -- -- -- --
   border  -1  0  0  1  1  2  3  2  3
   ======= == == == == == == == == ==


この境界配列は， :doc:`/Algorithms/Matching/KnuthMorrisPratt` の肝になっている．

- 素朴な方法 :download:`/Scripts/Python/border1.py`

.. literalinclude:: /Scripts/Python/border1.py
   :pyobject: border


- 線形時間の方法
- compute_border1 :download:`/Scripts/Python/compute_border1.py`

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

   
- compute_border2 :download:`/Scripts/Python/compute_border2.py`

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

   
.. raw:: html
         
         
		<div class="algorithm-sample">
		<script type="text/javascript"  src="../../_static/bord.js" > </script>

		<form onsubmit="return false;" autocomplete="off">
		<label> pattern = <input id="str_pattern" type="text" size="40" value="abababababb"/></label>
		<br />
		
		</form>
		<br />
		<div id="match_table" ></div>
		</div>

参考文献
--------
.. * XXXXX