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

接尾辞配列 (Suffix Array)
==================================================


.. .. index::
..   single: 接尾辞配列
..   single: Suffix Array
   
.. raw:: html

 	 <link rel="stylesheet" href="../_static/style.css" type="text/css" />

.. .. |logo| image:: ./suffix_array.png


.. raw:: html

		  <script type="text/javascript"  src="../_static/jquery.js" > </script>
		  <script type="text/javascript"  src="../_static/suffixArray.js" > </script>

		  <form onsubmit="return false;" autocomplete="off">
		  <label> str = <input id="str" type="text" size="64" value="a"/></label>
		  <br />
		  <label><input id="is_one_origin" type="checkbox" />1オリジンにする</label>
		  </form>
		  <br />
		  <div>
		  SA : <span id="sa_seq" style="word-wrap:break-word;" > </span>
		  <br/>
		  LCP : <span id="lcp_seq" style="word-wrap:break-word;" > </span>
		  <br/>
		  SA<sup>-1</sup> : <span id="sa_inv_seq" style="word-wrap:break-word;" > </span>
		  
		  </div>
		  <br />
		  <br />
		  <div id="sa_table" ></div>
		  

定義
-----------------------------------------

文字列wの接尾辞を，辞書式順序に並べ直したときの，接尾辞番号を配列として保存したもの．

.. もう少し正確な定義と，わかりやすい例を書くべき．




構築アルゴリズム 
-----------------------------------------
- 素朴な手法 :download:`/Scripts/Python/SA.py`

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

* LarssonSadakane法

.. literalinclude:: /Scripts/C++/LarssonSadakane.cpp
    :language: cpp

.. * todo:ちゃんとマルチキークイックソートで書く？

参考文献
-----------------------------------------

* N.J.Larsson and K.Sadakane. Faster suffix sorting. Technical report LU-CSTR:99-214, Dept. of Computer Science, Lund University, Sweden, 1999.