.. -*- coding: utf-8; -*-
接尾辞配列 (Suffix Array)
==================================================
.. .. index::
.. single: 接尾辞配列
.. single: Suffix Array
.. raw:: html
.. .. |logo| image:: ./suffix_array.png
.. raw:: html
SA :
LCP :
SA-1 :
定義
-----------------------------------------
文字列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.