Manacherアルゴリズムによる最長回文部分文字列の効率的探索
問題の定義
与えられた文字列から、連続する部分文字列の中で最も長い回文（前後どちらから読んでも同じになる文字列）を求める問題を「最長回文部分文字列問題」と呼ぶ。例えば文字列 "aaaba" では、"aaa" や "aba" が回文であり、その中で最長のものは "aaa" となる。
この問題は動的計画法でも解けるが、時間計算量が O(n²) となる。それに対して Manacher アルゴリズム ...
6月19日 21:07 投稿