スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Manacher のアルゴリズム

Manacher のアルゴリズムを勉強したので、理解したことをまとめておく。
このアルゴリズムを使えば、文字列に含まれる†1最長の回文 (longest palindrome) を効率的に求めることができる。

ただし、よくわからなかった部分は自分なりに改変したので、本来の Manacher のアルゴリズムとは少し違うかもしれない。

Tags : アルゴリズム プログラミング

奇数長の回文のみを考える。
文字列の各文字間にダミー文字を挿むことで、偶数長の回文は奇数長の回文に変換される。

たとえば、元の文字列を "abcd", ダミー文字を '#' とすれば、"#a#b#c#d#" を考えることになる。



記号

s : 入力された文字列
|s| : s の長さ
pali(i) : s[i] を中心とする最長回文
rad(i) : pali(i) の半径†2



アルゴリズムを理解するために、まず次の定理を示す。

定理
任意の i (0 ≦ i < n) に対して
rad(i)-k > rad(i-k) のとき rad(i+k) = rad(i-k).

注記 1
もちろん、rad(i-k), rad(i+k) が定義できるような k (0 ≦ k < n) のみを考えている。
つまり、
0 ≦ i-k ≦ i+k < n.

注記 2
定理の雰囲気を図示してみる。
examples
例 1.
s = "abbbcccbbba", i = 5, k = 3
を見ると、定理が何を言っているのかわかると思う。

例 2.
s = "abbbcccbbbc", i = 5, k = 3
は、定理の仮定 rad(i)-k > rad(i-k) が必要であることを示している。
つまり、pali(i-k) の左端は pali(i) の左端より真に右にある必要がある。

証明
・ rad(i+k) ≧ rad(i-k)
当たり前。

定理の仮定より pali(i-k) ⊂ pali(i) だから、
( これを言うだけなら rad(i)-k ≧ rad(i-k) でいい。 )
i について pali(i-k) と対称な位置にある文字列も回文であり、中心 : i+k, 半径 : rad(i-k).
rad(i+k) は中心が i+k である最長回文の半径なので、rad(i+k) ≧ rad(i-k).

・ rad(i+k) ≦ rad(i-k)
背理法。
rad(i+k) > rad(i-k) と仮定して矛盾を導く。

背理法の仮定より、中心 : i+k, 半径 : rad(i-k)+1 である回文 pali(i+k)' が存在。
( 回文の性質。奇数長の回文のみを考えていることに注意。 )
i について pali(i+k)' と対称な位置にある文字列 s(i-k)' を考えると、中心 : i-k, 半径 : rad(i-k)+1.
定理の仮定より s(i-k)' ⊂ pali(i).
( ここで rad(i)-k > rad(i-k) で置き換えられない。 )
ゆえに pali(i+k)' ⊂ pali(i) であり、s(i-k)' も回文。
これは rad(i-k) の最長性に反する。 ( pali(i-k) より長い回文が見つかってしまった。 ) [ 証明終 ]

この定理から、
rad(i)-k > rad(i-k) であるかぎり、rad(i+k) の値はただちに求められる。



擬似コード

以上をふまえて、Manacher のアルゴリズムの擬似コードを示す。

Manacher
begin
s にダミー文字を挿入する

i = 0, j = 0
while i < |s|
/* 素直な方法で rad[i] を求める */
while s[i-j] == s[i+j]
j=j+1
end while
rad[i] = j

/* 定理を用いて rad[i+k] を求める */
k = 1
while rad[i-k] < rad[i]-k
rad[i+k] = rad[i-k]
end while

/* k を進めた分 i を更新する */
i = i+k

/* j-k より小さい j は既にマッチしているので調べない */
j = max(j-k, 0)
end while

return max(rad[0], ..., rad[|s|-1])-1
end

自明ではないが、Manacher のアルゴリズムは O(|s|) 時間で動く。

最後の j = max(j-k, 0) は重要である。
ここを j = 0 としてしまうと、アルゴリズムの計算量は O(|s|2) になる。
( s = "aaaaaaa" というケースを考えてみればわかる。 )



C++ による実装例
int Manacher(const string &_s){
int n=_s.length(),i,j;
string s(2*n+1,'#');
for(i=0;i<n;i++) s[2*i+1]=_s[i];
n=2*n+1;

vector<int> rad(n);
for(i=j=0;i<n;){
while(0<=i-j && i+j<n && s[i-j]==s[i+j]) j++;
rad[i]=j;

int k;
for(k=1;i-k>=0 && rad[i-k]<rad[i]-k;k++) rad[i+k]=rad[i-k];

i+=k;
j=max(j-k,0);
}
return *max_element(rad.begin(),rad.end())-1;
}



参考サイト

Spaghetti Source - 最長回文 (Manacher)
Longest palindromic substring - PEG Wiki -
求最长回文子串的Manacher算法 - ywhorizen -



†1 : 部分文字列として含まれるという意味。 部分列としてであれば、Manacher は使えないが DP で解ける。
†2 : 文字列 s の半径 rad := ceiling(|s|/2) と定義する。半径という言葉の意味そのもの。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。