o(n)時間複雑度検索最大回文文字列(マラ車アルゴリズム)

Manacher’s Algorithmマラ車のアルゴリズム
このマラカーアルゴリズムManacher's Algorithmは、文字列の最長回文子列を検索するための線形方法であり、1975年にManacherという人によって発明されたもので、この方法の最大の貢献は時間の複雑さを線形に向上させることにあります.これは非常に素晴らしいものです.回文列については、よく知らないと思いますが、「bob」、「level」、「noon」などのような文字列を読んでいます.どのようにして文字列の中で一番長い回文子列を見つけられますか?各文字を中心に、回文子列を探してみてください.しかし、この方法の時間の複雑さはO(n＊n)で、あまり効率的ではありません.次に、時間の複雑さはO(n)のマラ車アルゴリズムを見てみます.マラドーナアルゴリズムは、(1)iがRの外にあり、暴力拡(2)IがRの中にあり、3つの場合に分けられます.a.i’回文はLにあり、Rの内b.i’回文はLにあり、Rの外c.i’回文は左境界とL圧線にあり、Rの右境界から拡大します.
回文列の長さは奇可偶で、例えば「bob」は奇数の回文で、「noon」は偶数の回文です.馬車アルゴリズムの第一歩は前処理です.作り方は各文字の左右に特殊な文字を加えます.
b o b-->((璣b菗b菗b菗)
noon-->((菗n菗o菗)
このようにする利点は、元の文字列が奇数であろうと偶数であろうと、処理後に得られた文字列の個数が奇数であることで、状況に関係なく議論され、一緒に処理することができるということです.次に、処理後の文字列tと同じ長さの配列pが必要です.p[i]はt[i]文字を中心とした回文サブストリングの半径を表します.p[i]=1であれば、回文サブストリングはt[i]自体です.簡単な例を見てみます.
『菗1菗2菗133751;2\33751;2\菽』1 2 1 2 2 2 2 2 2 2 2 2 1 1 1 2 2 1 2 2 2 1 2 2 2 2 1 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
なぜ私たちは回文節の半径に関心がありますか?上記の例を見ると、中間の「1」を中心とした回文子列「菘2123123;1123123;1123452;2{2〹」の半径は6ですが、?号を添加していない回文子列は「222222」です.長さは5で、半径1を減らします.これは普遍的な法則ですか?私たちは前の「菗b荍(菗b)」を見てみます.中間の「o」を中心とした回文列の半径は4で、「bob」の長さは3で、法則に合っています.偶数の場合は「n o n」を追加した後の回文列は「├」の中ほどです.完璧に法則に合う.ですから、一番大きな半径を見つけたら、一番長い回文の文字の数が分かります.長さだけがサブストリングの位置を特定できないことを知っています.また、サブストリングの開始位置を知る必要があります.
まず、中間の「1」は文字列の「萼1萼233751;1123123;2?2123;2〹2{2{」の中の位置は7で、半径は6で、7-6=1のようです.ちょうど回文子串の「22222222222222」は元の「1212122」の中の開始位置の1です.さて、「b o b」「o」の位置は3ですが、半径は4です.これはマイナスになります.間違いないです.だから、私たちは少なくとも中心の位置を後ろに移動しなければならないです.0です.前の方に文字を追加しなければならないです.この文字は「璣号」ではなく、sの中に登場する文字でもないので、とりあえず米ドルを使ってみましょう.やはり博主の一番好きなものです.これが同じでないとp値は変わりません.最後に対応するものを追加しますか?実は使わないのです.文字列の末尾は「\0」と表示されています.これはデフォルトと同じです.その時、「o」は「KaTeX parse error:Expected'EOF'で、got'儏儏'at position 1:33751;̲b萼の中の位置は4です.??????????????????????????????????????????????は2です.????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????同前の位置は5で、半径も5です.2で割っても0で割っても完璧です.他の例を試してもいいです.この法則に合っています.長男串の長さは半径1を減らして、スタート位置は中間位置から半径を引いて2を割ります.
では、p配列をどう求めるかを見てみます.補助変数mxとidを2つ追加する必要があります.ここでidは一番右側の位置に延びるその回文サブストリングの中心点位置です.mxは回文列が延びる一番右側の位置です.このアルゴリズムの一番核心の行は下の通りです.
p[i]=mx>i?min(p[2*id-i],mx-i):1;
これを理解すれば、マラドーナのアルゴリズムは基本的に問題ないと言えます.このラインのコードを分解してみてください.
mx>iであれば、p[i]=min(p[2*id-i],mx-i)
p[i]=1
mx-i>P[j]の場合、S[j]を中心とした回文サブストリングはS[id]を中心とした回文サブストリングに含まれていますので、iとj対称なので、S[i]を中心とした回文サブストリングは必ずS[id]を中心とした回文サブストリングに含まれています.ここで、j=2 id-iは、jとidの間の距離がidからiの間の距離に等しいので、i-idであるため、j=id-(i-id)=2 id-i.P[j]==mx-iの場合、S[j]を中心とする回文サブストリングは、必ずしもS[id]に完全に含まれるとは限らない.中心となる回文子列の中では対称性に基づいて、下図の二つの緑枠で囲まれている部分は同じであり、つまりS[i]を中心とした回文子列は、右側に少なくともmxの位置、つまりP[i]に拡張されます.=mx-i.mxの後の部分が対称かどうかは、大人しくマッチングするしかない.これは後からwhileのサイクルに続く役割である.mx<=iの場合、P[i]に対してより多くの仮定をすることができなくて、P[i]=1しかない.

#include 
#include 
#include 

using namespace std;

string Manacher(string s) {
    // Insert '#'
    string t = "$#";
    for (int i = 0; i < s.size(); ++i) {
        t += s[i];
        t += "#";
    }
    // Process t
    vector p(t.size(), 0);
    int mx = 0, id = 0, resLen = 0, resCenter = 0;
    for (int i = 1; i < t.size(); ++i) {
        p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
        while (t[i + p[i]] == t[i - p[i]]) ++p[i];
        if (mx < i + p[i]) {
            mx = i + p[i];
            id = i;
        }
        if (resLen < p[i]) {
            resLen = p[i];
            resCenter = i;
        }
    }
    return s.substr((resCenter - resLen) / 2, resLen - 1);
}

int main() {
    string s1 = "12212";
    cout << Manacher(s1) << endl;
    string s2 = "122122";
    cout << Manacher(s2) << endl;
    string s = "waabwswfd";
    cout << Manacher(s) << endl;
}

参照リンク