Manacherアルゴリズム学習ノート
11255 ワード
前言
M a n a c h e r Manacher Manacherアルゴリズムは、マラ車アルゴリズムとも呼ばれ、回文問題を解決する利器であり、文字列問題でもよく使われている.
最も重要なのは、簡単で分かりやすいアルゴリズムです.
暴力から始めましょう
文字列の中で最も長い文字列の長さを求めるにはどうすればいいですか?
くだらないことは、もちろん暴力です.
文字列の各文字または2文字をエコー列の中心として列挙し,両端文字が異なるまで外側に拡張することで,O(n 2)O(n^2)O(n 2)の時間的複雑度で答えを求めることができる.
また、一部の出題者は怠け者で、作ったデータは水で、暴力は速く走る可能性がある.
しかし、もし出題者があなたをカードにしようとしたら?たとえば、次のデータがあります.
このとき,M a n a c h e r Manacher Manacherアルゴリズムを用いる.
簡単な前処理
暴力の過程で、回文列の長さの奇偶性という煩わしい問題を発見することができます.これで2回操作する必要があり、とても面倒です.
どうしようかな?
私たちは1波の前処理を行う必要があります.
1文字列「HLAKNOI」を例にとると、文字列の長さのパリティの問題を解決するために、文字列に現れない文字を2文字ごとに挿入することができます(どんな文字でもいいので、「%」を推奨しますが、結局「%」(膜)は幸運をもたらすことができます).最初と最後に、同じ文字列に現れない文字を1つずつ追加します(これで境界を判断する必要はありません).
すると、元の文字列はこうなりました:「!%H%L%A%K%N%O%I%?」
これで、また返事を求めるのが便利になりました.
単純な小さな性質
前処理後の各文字からの返信半径をp p p配列で記録することができ、1つの文字列「abcbad」について、そのp p p配列は以下の通りである.
!
%
a
%
b
%
c
%
b
%
a
%
d
%
?
p p p
1
1
2
1
2
1
6
1
2
1
2
1
2
1
1
よく見ると、アルファベットp p pの値を1ずつ減らすと、このアルファベットを中心に得られる最長の文字列の長さになります!
この性質から,p p p配列のみを要求すると,文字列全体で最も長いエコー列長を迅速に求めることができると考えられる.
M a n a c h e r Manacher Manacherアルゴリズムの核心思想
簡単な前処理を用いて,簡単な小さな性質を理解し,M a n a c h e r Manacher Manacherアルゴリズムの核心思想を理解し始めることができた.
まず、暴力がなぜ遅いのかという問題を考えなければなりません.
答えは簡単そうだ.暴力は解く過程で、多くの場所に何度も訪問するからだ.
では、一度だけ訪問していただけないでしょうか.
M a n a c h e r Manacher Manacherアルゴリズムはこの考えに基づいている.
M a n a c h e r Manacher Manacherアルゴリズムの大まかな考え方
第1ステップでは,解いた位置で生成された回文列が到達できる最大右境界を変数M a x Maxで記録し,回文列の中心位置i d idを記録した.
ここで,新しい位置x x xを解くと仮定すると,左から右へ操作するため,x>i d x>id x>idを保証できるが,x x xとM a x Max Maxの大きさの関係は確定しにくいため,分類して議論する. x > M a x x>Max x>Max この場合,x x xを中心とした回文列がまだ解明されていないことを示し,x x x暴力を解く. この場合の操作時間は複雑度が高いが、この場合の出現回数が多ければ多いほど平均操作時間は少なくなり、ほぼ反比例するため、時間複雑度は保証される.
x < M a x xこの場合、id idに関するx xの対称点2∗i d−x 2*id−x 2∗id−xを見つけることができ、2∗i d−x 2*id−x 2∗id−xを中心とした最長の文列の長さを再び分類して議論する: 2 2 2∗i d−x 2*id−x 2∗id−xを中心とした最長回文列の長さは小さく、この回文列はi d idを中心とした最長回文列の左半分の範囲内である エコー列の性質により,p x≧p 2∗i d−x p_を決定できた.x≥p_{2*id-x} px≥p2∗id−x ですので、p x p_をx pxはp 2∗i d−x p_に割り当てられる{2*id-x}p 2∗id−xを両側に拡張し続けた 2 2 2∗i d−x 2*id−x 2∗id−xを中心とした最長回文列の長さは小さく、この回文列はi d idを中心とした最長回文列の左半分の範囲外である この場合、i d idを中心とする最長回文列の右半分の範囲内のx xを中心とする列が回文列 であることを保証するしかない.ですので、p x p_をx pxはp i d+i d−x p_に付与する{id}+id-x pid+id−x.
実は上の2つの状況を直接p x p_にまとめることができますx pxは、m i n(p 2∗i d−x,p i d+i d−x)min(p_{2*id−x},p_{id}+id−x)min(p 2∗id−x,pid+id−x)として与えられる.
M a n a c h e r Manacher Manacherアルゴリズムの大まかな考え方はこのようにして、まだ分からないところがあれば、自分でもっと考えて理解することができます.
コード実装
M a n a c h e r Manacher Manacherアルゴリズムは、マラ車アルゴリズムとも呼ばれ、回文問題を解決する利器であり、文字列問題でもよく使われている.
最も重要なのは、簡単で分かりやすいアルゴリズムです.
暴力から始めましょう
文字列の中で最も長い文字列の長さを求めるにはどうすればいいですか?
くだらないことは、もちろん暴力です.
文字列の各文字または2文字をエコー列の中心として列挙し,両端文字が異なるまで外側に拡張することで,O(n 2)O(n^2)O(n 2)の時間的複雑度で答えを求めることができる.
また、一部の出題者は怠け者で、作ったデータは水で、暴力は速く走る可能性がある.
しかし、もし出題者があなたをカードにしようとしたら?たとえば、次のデータがあります.
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa......aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa(50000 a)
このとき,M a n a c h e r Manacher Manacherアルゴリズムを用いる.
簡単な前処理
暴力の過程で、回文列の長さの奇偶性という煩わしい問題を発見することができます.これで2回操作する必要があり、とても面倒です.
どうしようかな?
私たちは1波の前処理を行う必要があります.
1文字列「HLAKNOI」を例にとると、文字列の長さのパリティの問題を解決するために、文字列に現れない文字を2文字ごとに挿入することができます(どんな文字でもいいので、「%」を推奨しますが、結局「%」(膜)は幸運をもたらすことができます).最初と最後に、同じ文字列に現れない文字を1つずつ追加します(これで境界を判断する必要はありません).
すると、元の文字列はこうなりました:「!%H%L%A%K%N%O%I%?」
これで、また返事を求めるのが便利になりました.
単純な小さな性質
前処理後の各文字からの返信半径をp p p配列で記録することができ、1つの文字列「abcbad」について、そのp p p配列は以下の通りである.
!
%
a
%
b
%
c
%
b
%
a
%
d
%
?
p p p
1
1
2
1
2
1
6
1
2
1
2
1
2
1
1
よく見ると、アルファベットp p pの値を1ずつ減らすと、このアルファベットを中心に得られる最長の文字列の長さになります!
この性質から,p p p配列のみを要求すると,文字列全体で最も長いエコー列長を迅速に求めることができると考えられる.
M a n a c h e r Manacher Manacherアルゴリズムの核心思想
簡単な前処理を用いて,簡単な小さな性質を理解し,M a n a c h e r Manacher Manacherアルゴリズムの核心思想を理解し始めることができた.
まず、暴力がなぜ遅いのかという問題を考えなければなりません.
答えは簡単そうだ.暴力は解く過程で、多くの場所に何度も訪問するからだ.
では、一度だけ訪問していただけないでしょうか.
M a n a c h e r Manacher Manacherアルゴリズムはこの考えに基づいている.
M a n a c h e r Manacher Manacherアルゴリズムの大まかな考え方
第1ステップでは,解いた位置で生成された回文列が到達できる最大右境界を変数M a x Maxで記録し,回文列の中心位置i d idを記録した.
ここで,新しい位置x x xを解くと仮定すると,左から右へ操作するため,x>i d x>id x>idを保証できるが,x x xとM a x Max Maxの大きさの関係は確定しにくいため,分類して議論する.
M a n a c h e r Manacher Manacherアルゴリズムの大まかな考え方はこのようにして、まだ分からないところがあれば、自分でもっと考えて理解することができます.
コード実装
class Class_Manacher//Manacher
{
private:
int len,p[(N<<1)+5];
char ns[(N<<1)+5];
inline void Init(string st)//
{
register int i,l=st.length();
for(ns[i=0]='!',ns[len=1]='%';i<l;++i) ns[++len]=st[i],ns[++len]='%';
ns[++len]='?';
}
public:
inline int GetAns(string st)//
{
register int i,ans=0,id,Max=0;
for(Init(st),i=1;i<len;++i)
{
p[i]=i<=Max?min(p[(id<<1)-i],p[id]+id-i):1;// ， p[i]
while(!(ns[i-p[i]]^ns[i+p[i]])) ++p[i];//
if(i+p[i]>Max) Max=i+p[id=i];//
}
for(i=1;i<len;++i) ans=max(ans,p[i]);// p[i]
return ans-1;// p[i] 1
}
}Manacher;