Manacherのアルゴリズムを理解する
文字列sから最長の回文部分文字列を見つける問題について、Manacherのアルゴリズムはその解法の一つです。このアルゴリズムは1957年にManacherによって考案され、時間計算量が線形O(n)に改善されます。
問題
入力: 文字列 s
出力: s の最長の回文部分文字列
例
例 1:
入力: s = "babad"
出力: "bab" または "aba"
例 2:
入力: s = "cb ...
6月23日 17:43 投稿
Manacherアルゴリズムによる最長回文部分文字列の効率的探索
問題の定義
与えられた文字列から、連続する部分文字列の中で最も長い回文（前後どちらから読んでも同じになる文字列）を求める問題を「最長回文部分文字列問題」と呼ぶ。例えば文字列 "aaaba" では、"aaa" や "aba" が回文であり、その中で最長のものは "aaa" となる。
この問題は動的計画法でも解けるが、時間計算量が O(n²) となる。それに対して Manacher アルゴリズム ...
6月19日 21:07 投稿