Manacherアルゴリズムによる回文解析の効率的処理
問題の背景
文字列 s が与えられ、その中にある最長の連続する回文部分文字列の長さを求めたいとします。単純なアプローチとしては、すべての部分文字列を列挙し、それぞれが回文かどうかを判定する方法がありますが、これは O(n^3) の計算量となり非効率です。
より良い方法として、各位置を中心として左右に拡張していく O(n^2) アルゴリズムが考えられます。この方法で ...
6月8日 23:54 投稿
接尾辞配列とその応用
接尾辞配列
単一文字列の部分文字列に関する辞書順問題に一般的に利用できます。
アルゴリズムの流れ
まず、文字列のすべての接尾辞をソートします。
定義：\(sa[i]\) はすべての接尾辞をソートした後、第 \(i\) 番目に小さい接尾辞のインデックスを表します。\(rk[i]\) は接尾辞 \(i\) のランクを表します。
倍増法と基数ソート（\(O(n\log n)\)）を採用します（簡略化/エ ...
5月23日 21:50 投稿