Manacherアルゴリズム(マラーアルゴリズム)説明
2989 ワード
Manacherアルゴリズム:文字列内のエコーシーケンスの最大値を効率的に見つけるアルゴリズムです.時間的複雑度はO(n)である.
文字列の文字列に対する通常の求め方です.iから両端に延びるペアです.時間が複雑で多くの問題を乗り越えられない.だからmanacherアルゴリズムの優位性が現れます.
私たちは毎回i点から両側に拡張する必要がないかどうかを考えることができます.答えはいいです.前に計算した文字列長を用いて,現在の文字列長の検索を最適化することができる.
このアルゴリズムを詳しく話す前に.データ構造とその意味を明確にします.
p【i】:iを中点とする回文列の長さを表す.
mx:現在の文字列の右端の位置.
id:現在最も右端の文字列の中点位置.
はい、上の概念は理解しなくても大丈夫ですが、彼らはそれぞれ何を代表しているかを覚えておいてください.
Manacherアルゴリズムの最初のステップ:元の文字列の前処理.文字の間に#番号を追加します.具体的には、単一の二重文字列の問題を解決するために使用されます.例を挙げるとわかる.
例えば、文字列abaについては、処理後に@#a#b#a#となる.文字列の数は奇数です.
文字列ababでは、処理後に@#a#b#a#b#となる.文字列の数は奇数です.
注意深く同級生が気づく.どうして前に@があるのですか.s【0】='@'.を選択すると、文字列の下付き文字列の処理が便利になります.
Mancherアルゴリズムの第2のステップ:配列を巡る.任意のi位置について.id対称に関するiの位置jを取得する.idは半径長mx−idの回文列であるからである.従ってi位置の返信状況はid対称点jに関する返信状況と等しい.例を挙げる
@ # b # a # b # a # e # a # b # a # b #;
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
j id i mx
id-(i-id)
p【】 3 3
i=14の場合
p【i】 = p【id-(i-id)】= 3;
しかし、これはその一つの状況にすぎない.
もう1つ例を挙げます.
@ # e # a # b # a # e # a # b # a # d #
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
j id i mx
id-(i-id)
p【】 5 3
どうしてこんなことになったのですか.
この例では,i=14の場合,現在最も長い回文列ではidを中心とした半径長がmx−idであることが分かった.だからeという文字の両側のabaについてはきっと等しいに違いない.しかし,左側のbを中心とした回文列の長さが両側のaにしかならないことは保証できない.この回文列はもっと長いかもしれません.これにより、左のbにおけるp【j】の値がp【i】に等しくない.しかし、私たちが知っているのは、2つのabaが一定に等しいことです.
だからこの2つの状況を総合します.我々は
p【i】 = min(mx-i ,p【id-(i - id)】);
もちろんこれはmx>iの場合です
この場合ではない
p【i】 = 1;
manacherアルゴリズムはここで完成しましたか?naiveはあと一歩.さらに両側に探して、つまりi点を伸ばす回文列です.次に、idとmxを更新する値を比較します.
具体的な実装手順を見てみましょう.
文字列の文字列に対する通常の求め方です.iから両端に延びるペアです.時間が複雑で多くの問題を乗り越えられない.だからmanacherアルゴリズムの優位性が現れます.
私たちは毎回i点から両側に拡張する必要がないかどうかを考えることができます.答えはいいです.前に計算した文字列長を用いて,現在の文字列長の検索を最適化することができる.
このアルゴリズムを詳しく話す前に.データ構造とその意味を明確にします.
p【i】:iを中点とする回文列の長さを表す.
mx:現在の文字列の右端の位置.
id:現在最も右端の文字列の中点位置.
はい、上の概念は理解しなくても大丈夫ですが、彼らはそれぞれ何を代表しているかを覚えておいてください.
Manacherアルゴリズムの最初のステップ:元の文字列の前処理.文字の間に#番号を追加します.具体的には、単一の二重文字列の問題を解決するために使用されます.例を挙げるとわかる.
例えば、文字列abaについては、処理後に@#a#b#a#となる.文字列の数は奇数です.
文字列ababでは、処理後に@#a#b#a#b#となる.文字列の数は奇数です.
注意深く同級生が気づく.どうして前に@があるのですか.s【0】='@'.を選択すると、文字列の下付き文字列の処理が便利になります.
Mancherアルゴリズムの第2のステップ:配列を巡る.任意のi位置について.id対称に関するiの位置jを取得する.idは半径長mx−idの回文列であるからである.従ってi位置の返信状況はid対称点jに関する返信状況と等しい.例を挙げる
@ # b # a # b # a # e # a # b # a # b #;
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
j id i mx
id-(i-id)
p【】 3 3
i=14の場合
p【i】 = p【id-(i-id)】= 3;
しかし、これはその一つの状況にすぎない.
もう1つ例を挙げます.
@ # e # a # b # a # e # a # b # a # d #
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
j id i mx
id-(i-id)
p【】 5 3
どうしてこんなことになったのですか.
この例では,i=14の場合,現在最も長い回文列ではidを中心とした半径長がmx−idであることが分かった.だからeという文字の両側のabaについてはきっと等しいに違いない.しかし,左側のbを中心とした回文列の長さが両側のaにしかならないことは保証できない.この回文列はもっと長いかもしれません.これにより、左のbにおけるp【j】の値がp【i】に等しくない.しかし、私たちが知っているのは、2つのabaが一定に等しいことです.
だからこの2つの状況を総合します.我々は
p【i】 = min(mx-i ,p【id-(i - id)】);
もちろんこれはmx>iの場合です
この場合ではない
p【i】 = 1;
manacherアルゴリズムはここで完成しましたか?naiveはあと一歩.さらに両側に探して、つまりi点を伸ばす回文列です.次に、idとmxを更新する値を比較します.
具体的な実装手順を見てみましょう.
#include
#include
#include
using namespace std;
const int N = 20000005;
char str[N];
int p[N];
void
manacher(char *s,int len){
p[0] = 1;
int mx = 0 , id = 0;
for(int i = 1 ;i < len ; i ++){
p[i] = mx > i ? min(p[id*2 - i],mx-i) : 1;
while(s[i+p[i]] == s[i-p[i]])
p[i] ++;
if(i+p[i] > id + p[id]){
id = i;
mx = i +p[i];
}
}
}
int main(){
while(scanf("%s",str)){
int len = strlen(str);
for(int i = len ; i >= 0; i --){
str[(i << 1) + 1] = '#';
str[(i << 1) + 2] = str[i];
}
str[0] = '@';
len = len*2 +2;
manacher(str,len);
int ans = 0;
for(int i = 0 ; i < len ; i++)
ans = max(ans,p[i]-1);
printf("%d
",ans);
}
return 0;
}