接尾辞配列。これを使えば, 文字列に対するいろいろなクエリが早く出来るので調べてみてね。一般的には $O(N \log^2 N)$ の実装が知られているがこれは蟻本参照。また, SA-IS と呼ばれる $O(N) $ のヤバイ実装が存在するが, ヤバイ(大事なことなので 2 度言った)ので $O(N \log N)$ で妥協している。よほどのことがない限り$O(N \log N)$ の実装で十分だと思われる。