Simple Linear Work Suffix Array Construction (Juha Kärkkäinen, Peter Sanders)

線形時間で接尾辞配列を作る”シンプルな”アルゴリズム。
シンプルな、というのが重要。
いままで見かけたアルゴリズムは、複雑で、すぐには理解できなかった。
このアルゴリズムは1時間読んで理解できた。
このアルゴリズムに少し付け加えると、LCPも線形時間でできるらしい。
via 武田先生＠梅村研の博士論文