トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

GeeksforGeeks(Manacherアルゴリズム)

[GeeksforGeeks]

GeeksforGeeks(Manacherアルゴリズム)

マネカーのアルゴリズム - 線形時間の最長回文部分列 - part1

文字列が与えられたとき、回文の最長部分列を見つける

  • "forgeeksskeegfor" の場合、"geeksskeeg"
  • "abaaba" の場合、"abaaba"
  • "abababa" の場合、"abababa"
  • "abcbabcbabcba" の場合、"abcbabcba"

すでに私たちは素朴な方法(O(N^3))や指数時間(O(N^2))の方法について議論した(Set1, Set2)。この記事では、線形時間で最長回文部分列を見つけるマネカーのアルゴリズムについて話す。

回文を検出する1つの方法(Set2)としては、文字列の中央から処理を始め1つずつ両方の方向へ文字を比較するものがある。

ここに文字列の中央が4番目の"b"という文字(0-indexedだと3番目)がある。ここで左右に文字を一致させていけば、すべての文字が一致するので"abababa"は回文であるといえる。

ここで中央の位置は実際の文字の位置になるとは限らない、2つの文字の間になることもありうる。"abaaba"の半分の長さを考える。この文字列は3と4番目の文字"a"の間の位置を中心にして回文になっている。

長さNの文字列について最長回文部分列を見つけるためには、2*N + 1の中央要素(というのはN個の文字の位置、N-1の文字と文字の間の位置、そして2つの文字列の開始/終了位置をあわせたものである)すべての場合を考える方法がある。このすべての場合の数2*N+1について左右の方向へ文字の一致を試み最長回文部分列の状態を保持する。この方法はO(N^2)の時間がかかり、それはSet2で行った内容と同じになる。

以下のような2つの文字列、"abababa"と"abaaba"を考えてみよう:

この2つの文字列において、中央位置の左右(1つ目の文字列の位置7、2つの文字列の位置6)は対称的です。なぜでしょう?なぜならその全体の文字列は中央位置を中心にして回文になっているからです。2*N+1の位置について左右の方向へ最長回文部分列の算出を行う必要があるとすれば、回文の左右対称である特徴は不必要な計算を削減するための助けになるでしょう(例えば文字の比較)。

ltp1.jpg ltp2.jpg ltp3.jpg ltp4.jpg
お名前: コメント: