接尾辞配列
長さ11の文字列
を例に取って説明する。先頭から一文字ずつ削ってみればわかるように、この文字列は "abracadabra", "bracadabra", "racadabra", ......, "ra", "a" という11の接尾辞を持つと考えられる。この11の接尾辞を、それぞれの開始位置(1~11)とともに配列に順次格納し、接尾辞について辞書順に並べ替えると以下のようになる。表中の最長共通接頭辞(LCP)は、直前の接尾辞と、接尾辞の先頭から何文字か共通する文字がある場合の最大文字数。
元の文字列があれば、接尾辞の開始位置を指定することですべての接尾辞を余すことなく得ることができる。この接尾辞を辞書順に並べたときの開始位置の配列が接尾辞配列となる。
"abracadabra"に対する接尾辞配列は、表のように、(11, 8, 1, 4, 6, 9, 2, 5, 7, 10, 3) となる。接尾辞 "a" の開始位置は11で、接尾辞 "abra" の開始位置は8だからである。
"abracadabra"に対して、12番目の接尾辞として空文字を考えることができる。しかし、これは常に先頭に配置されることになるので特に情報を持たないので、省略しても問題ない。