Ukkonen's algorithm to construct Suffix Tree

概念
対象文字列の最後尾に1文字増えたとき、接尾辞木を更新する。
ただし、ここでの接尾辞木は終端文字を含まず、葉以外のノードで接尾辞が終わることもあるような木である。
対象文字列にxが追加されたとき、それまでの任意の接尾辞aをaxに変えることがこのアルゴリズムの目的。
1. aが葉で終わる接尾辞のとき …… 葉の終端枝にxを追加するだけ
2a. aが葉ではなく、xで始まる枝が出ていない分岐ノードで終わるとき …… x の枝を追加する
2b. aが枝の途中で終わるとき …… ノードを作り、それまでの枝の続きとxの枝を追加する
3. それ以外、すなわちaがxで始まる枝を持つノードで終わるとき … なにもしない