SA-IS 法のメモ - まめめも

suffix array を線形時間で構築する SA-IS 法についてのメモです。 SA-IS 法の解説はわりと世の中にいっぱいありますが、実際のプログラムにする方法がよくわからなったり、どうしてそれでうまく行くのか書かれてなくて気持ち悪かったりするものが多くて、自分の望む感じのものがありませんでした。アルゴリズムは当然プログラムで見たいし、厳密な証明は要らないけど直観的な理由は知りたい。 ということで、自分なりの理解を書いてみました。 suffix array とは 文字列の suffix とは、文字列の途中から最後までの部分文字列のことです。題材の文字列を "mmiissiissiippii" とすると、次の 17 個の部分文字列です。 0 mmiissiissiippii$ 1 miissiissiippii$ 2 iissiissiippii$ 3 issiissiippii$ 4

[odz]

“これ”