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

接尾辞トライ (Suffix Trie)
==================================================


.. .. index::
..   single: 接尾辞トライ
..   single: suffix trie

.. .. |logo| image:: ./suffix_trie.png

.. 文字列wのすべての接尾辞に対するトライ

.. .. |logo|


.. raw:: html

    <script type="text/javascript" src="../_static/suffixTrie.js"></script>
    <script type="text/javascript">
    (function(){
        window.addEventListener("load", function() {
            function update(){
                var w = $("#w").val();
                $("wlength").text( w.length );
                $("suffixTrieAA").html( "" );
                var st = new SuffixTrie(w);
                drawSuffixTrie(st);
            }
            $("input").change( update );
            $("#w").keyup( update );
            update();
        })
    })()
    </script>



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

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

    <div>
    <canvas id="sample" width="800" height="600"></canvas>
    </div>


    <suffixTrieAA>
    dummyAA
    </suffixTrieAA>


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


接尾辞トライのオンライン構築アルゴリズム
--------------------------------------------------------

:download:`/Scripts/CoffeeScript/SuffixTrie.coffee` 



.. highlight:: coffee-script

.. literalinclude:: /Scripts/CoffeeScript/SuffixTrie.coffee
   :language: coffee-script
   :linenos:
   :lines: 1-94