アルゴリズム——Manacherアルゴリズム
3436 ワード
列挙中心位置では,文字列の長さが奇数か偶数かを特に考慮する必要があるため,コード実装を記述する際に奇数と偶数の場合を別々に記述する方法があり,長さが奇数か偶数かを問わず統一的に処理できるかどうか.例えば、すべての状況を奇数処理に変換できますか?
答えは肯定的だ.これが次に示すManacherアルゴリズムであり,このアルゴリズムが最長回文サブ列を求める時間複雑度は線形O(N)である.
まず、各文字の両側に特殊な記号を挿入することによって、可能な奇数または偶数の長さのすべての回文サブ列を奇数の長さに変換します.例えばabbaがa#b#b#a#になり、abaがa#b#a#になる.
また、符号化の複雑さをさらに低減するために、文字列の開始に別の特殊文字を加えることができ、$#a#b#a#などの境界問題を特別に処理する必要がない.
文字列1222321を例にとると、＃と$の2つの特殊記号が挿入されてS[]=「$#1#2#2#2#3#2#1」となり、文字S[i]を中心とした最長回文サブ列の左または右に拡張された長さ(S[i]を含む)が1つの配列P[i]で記録される.
例えばSとPの対応関係:
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
P[i]-1は、元の文字列の中で最も長い文字列の総長さであり、5であることがわかる.
次にP[i]をどのように計算しますか?Manacherアルゴリズムは2つの補助変数idとmxを増加させ、idは最大回文サブ列の中心の位置を表し、mxはid+P[id]、すなわち最大回文サブ列の境界である.重要な結論が得られました
mx>iの場合、P[i]>=Min(P[2*id-i],mx-i)Cコードは以下の通りである.
以下、j=2*id−i、すなわちjをidに関するiの対称点とする.
mx-i>P[j]の場合、S[j]を中心とした回文サブストリングは、S[id]を中心とした回文サブストリングに含まれ、iとjが対称であるため、S[i]を中心とした回文サブストリングは必ずS[id]を中心とした回文サブストリングに含まれるので、P[i]=P[j]が必要となる.
P[j]>=mx−iの場合、S[j]を中心とした回文サブストリングは必ずしもS[id]を中心とした回文サブストリングに完全に含まれるとは限らないが、対称性から、下図の2つの緑枠で囲まれた部分は同じであり、すなわちS[i]を中心とした回文サブストリングは、右に少なくともmxの位置、すなわちP[i]>=mx−iに拡張することが分かる.mxの後の部分が対称かどうかについては、具体的に一致します.
また,mx<=iの場合,P[i]をより多く仮定できないため,P[i]=1にしてからマッチングするしかない.
以上、キーコードは以下の通りです.
このManacherアルゴリズムはid,mxを組み合わせて,各サイクルにおいてP[i]の高速値を直接与えることができ,iを中心とした回文サブストリングを計算する過程で毎回1から比較する必要がなく,比較回数を減らし,最終的に最長回文サブストリングを解く長さが線形O(N)に達する時間の複雑さをもたらす.
答えは肯定的だ.これが次に示すManacherアルゴリズムであり,このアルゴリズムが最長回文サブ列を求める時間複雑度は線形O(N)である.
まず、各文字の両側に特殊な記号を挿入することによって、可能な奇数または偶数の長さのすべての回文サブ列を奇数の長さに変換します.例えばabbaがa#b#b#a#になり、abaがa#b#a#になる.
また、符号化の複雑さをさらに低減するために、文字列の開始に別の特殊文字を加えることができ、$#a#b#a#などの境界問題を特別に処理する必要がない.
文字列1222321を例にとると、＃と$の2つの特殊記号が挿入されてS[]=「$#1#2#2#2#3#2#1」となり、文字S[i]を中心とした最長回文サブ列の左または右に拡張された長さ(S[i]を含む)が1つの配列P[i]で記録される.
例えばSとPの対応関係:
S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 #
P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1
P[i]-1は、元の文字列の中で最も長い文字列の総長さであり、5であることがわかる.
次にP[i]をどのように計算しますか?Manacherアルゴリズムは2つの補助変数idとmxを増加させ、idは最大回文サブ列の中心の位置を表し、mxはid+P[id]、すなわち最大回文サブ列の境界である.重要な結論が得られました
mx>iの場合、P[i]>=Min(P[2*id-i],mx-i)Cコードは以下の通りである.
//mx > i， P[i] >= MIN(P[2 * id - i], mx - i)
//
if (mx - i > P[2*id - i])
P[i] = P[2*id - i];
else //mx-i <= P[2*id - i]
P[i] = mx - i; 以下、j=2*id−i、すなわちjをidに関するiの対称点とする.
mx-i>P[j]の場合、S[j]を中心とした回文サブストリングは、S[id]を中心とした回文サブストリングに含まれ、iとjが対称であるため、S[i]を中心とした回文サブストリングは必ずS[id]を中心とした回文サブストリングに含まれるので、P[i]=P[j]が必要となる.
P[j]>=mx−iの場合、S[j]を中心とした回文サブストリングは必ずしもS[id]を中心とした回文サブストリングに完全に含まれるとは限らないが、対称性から、下図の2つの緑枠で囲まれた部分は同じであり、すなわちS[i]を中心とした回文サブストリングは、右に少なくともmxの位置、すなわちP[i]>=mx−iに拡張することが分かる.mxの後の部分が対称かどうかについては、具体的に一致します.
また,mx<=iの場合,P[i]をより多く仮定できないため,P[i]=1にしてからマッチングするしかない.
以上、キーコードは以下の通りです.
// ， s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++)
{
p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
while (s[i + p[i]] == s[i - p[i]])
p[i]++;
if (i + p[i] > mx)
{
mx = i + p[i];
id = i;
}
}
// p[i] このManacherアルゴリズムはid,mxを組み合わせて,各サイクルにおいてP[i]の高速値を直接与えることができ,iを中心とした回文サブストリングを計算する過程で毎回1から比較する必要がなく,比較回数を減らし,最終的に最長回文サブストリングを解く長さが線形O(N)に達する時間の複雑さをもたらす.