接尾辞木 - Wikipedia

文字列 BANANA に $ を補った接尾辞木。根から葉（四角で表示）への6つの経路が6つの接尾辞 A$, NA$, ANA$, NANA$, ANANA$, BANANA$ に対応。四角の中の数字は対応する接尾辞の開始位置を示す。接尾辞リンクは破線の矢印で示されている。 接尾辞木（せつびじき）またはサフィックス木（英: Suffix tree）は、与えられた文字列の接尾部を木構造(基数木)で表すデータ構造であり、多くの文字列操作の高速な実装に利用されている。 文字列 の接尾辞木は木構造であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ の接尾部の1つが対応している。従って、これは の接尾部に関する基数木である。 文字列 からそのような木構造を構築するには、 の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される（ の部分文字列を探す、誤

[mooz]

任意の部分文字列の探索。頻度カウントも。

[Sampo]

接尾辞木ってのを構築すると速いらしい