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

接尾辞木 (Suffix Tree)
==================================================


.. .. index::
..   single: 接尾辞木
..   single: suffix tree

.. .. |logo| image:: ./suffix_tree.png

.. 接尾辞トライの分岐のない内部頂点を削除したもの．

.. .. |logo|

.. raw:: html

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


文字列を入力してください．（色分けはアルファベットサイズ10までですが，接尾辞木そのものは大きなアルファベットに対しても正しく構築しています）
   
.. raw:: html

   <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>
   <canvas id="sample" width="800" height="600"></canvas>
   </div>


..   <H3>  SuffixTree をAAで描画するテスト</H3>
   <suffixTreeAA>
   dummyAA
   </suffixTreeAA>

定義
----------------------------------------------------
アルゴリズム
----------------------------------------------------


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

.. raw:: html

	<ul>
	<li>	
		P. Weiner. Linear pattern matching algorithms. In Switching and Automata Theory,
		1973. SWAT'08. IEEE Conference Record of 14th Annual Symposium on, pages 1–11. IEEE, 1973.　
		<a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4569722" target="_blank">link</a><BR>
	</li>
	<li>	
		Ukkonen, Esko. On-line construction of suffix trees. Algorithmica, 1995, 14.3: 249-260.
		<a href="http://link.springer.com/article/10.1007/BF01206331" target="_blank">link</a><BR>
	</li>	
	<li>
		McCreight, Edward M. A space-economical suffix tree construction algorithm. Journal of the ACM (JACM), 1976, 23.2: 262-272.
		<a href="http://dl.acm.org/citation.cfm?id=321946" target="_blank">link</a><BR>
	</li>
	</ul>