接尾辞配列とその応用
接尾辞配列
単一文字列の部分文字列に関する辞書順問題に一般的に利用できます。
アルゴリズムの流れ
まず、文字列のすべての接尾辞をソートします。
定義：\(sa[i]\) はすべての接尾辞をソートした後、第 \(i\) 番目に小さい接尾辞のインデックスを表します。\(rk[i]\) は接尾辞 \(i\) のランクを表します。
倍増法と基数ソート（\(O(n\log n)\)）を採用します（簡略化/エ ...
5月24日 06:50 投稿
奇想天外なアイデアがコードで現実になる場所
5月24日 06:50 投稿