接尾辞木

接尾辞木（せつびじき）またはサフィックス木（Suffix tree）は、与えられた文字列の接尾部を木構造(基数木)で表すデータ構造であり、多くの文字列操作の高速な実装に利用されている。文字列 <math>S</math> の接尾辞木は木構造であり、その枝には文字列が対応し、木構造の根から葉までの経路ごとにそれぞれ <math>S</math> の接尾部の1つが対応している。従って、これは <math>S</math> の接尾部に関する基数木である。文字列 <math>S</math> からそのような木構造を構築するには、<math>S</math> の長さに対して線形な時間と空間を要する。構築できれば、いくつかの操作が高速化される（<math>S</math> の部分文字列を探す、誤字をある程度許容した上での部分文字列特定、正規表現パターンとのマッチングなど）。接尾辞木は最長共通部分文字列問題の線形な解法の1つでもある。これらの高速化の代償として、接尾辞木に要するメモリ空間は文字列そのものを格納するのに要するメモリ空間よりもかなり大きくなる。