接尾辞配列
接尾辞配列を構築する最も容易な方法は、効率的な比較ソートを利用することである。この場合、 O ( n log  n ) {\displaystyle O(n\log n)} 回の接尾辞の比較が必要になるが、接尾辞の比較は O ( n ) {\displaystyle O(n)} の時間が必要となる。従って全体的な計算時間は O ( n 2 log  n ) {\displaystyle O(n^{2}\log n)} となる。より精巧なアルゴリズムでは、部分ソートの結果の重複した比較を避けることで O ( n log  n ) {\displaystyle O(n\log n)} に改善できる。接尾辞木から変換する事で O ( n ) {\displaystyle O(n)} で変換する事も出来る。
2009年に Ge Nong らが SA-IS 法を発表した。これにより計算量は O ( n ) {\displaystyle O(n)} 、メモリ使用量は max { 2 n , 4 k } {\displaystyle \max\{2n,4k\}} (kは文字の種類数)となり、100行程度のC言語のプログラムで実装できる。Yuta Mori が論文発表と同時に SA-IS 法の実装を公開しており、論文でも言及されている。
接尾辞配列を使えば検索対象文字列の出現位置を高速に検索することができる。接尾辞配列においては、文字列が出現する位置を求めることはつまり、その文字列で始まっている接尾辞を求めることと同じである。接尾辞配列は辞書順にソートされているので、検索対象となる文字列の検索には、高速な二分探索アルゴリズムが利用できる。 m {\displaystyle m} を検索文字列の長さとすると、単純な実装では二分探索で O ( m log  n ) {\displaystyle O(m\log n)} の計算時間になる。
直前の接尾辞と、接尾辞の先頭から何文字か共通する文字がある場合、その最大文字数を最長共通接頭辞(LCP, Longest Common Prefix)と呼ぶが、あらかじめ求めておいたLCPにより無駄な比較を省き検索を高速化することができる。このとき、 O ( m + log  n ) {\displaystyle O(m+\log n)} の時間で検索できる。