線形時間で接尾辞配列を作る”シンプルな”アルゴリズム。 シンプルな、というのが重要。 いままで見かけたアルゴリズムは、複雑で、すぐには理解できなかった。 このアルゴリズムは1時間読んで理解できた。 このアルゴリズムに少し付け加えると、LCPも線形時…

接尾辞配列上での隣接要素のLCPは配列で記憶できる。 任意区間のLCPは、区間内の隣接LCPの最小値。 統合文字列がLCPの直後にある場合、そのような区間のうち極大な区間をまるごと移動。 どこへ？ … 2分探索？ 移動した後、即座に整合性維持？ ← 移動されたも…