72

Manacher のアルゴリズムを理解するのに約 6 ～ 8 時間費やした後、タオルを投げる準備が整いました。しかし、その前に、最後にもう 1 つ、暗がりで説明します。誰か説明してもらえますか? コードは気にしません。誰かにALGORITHMについて説明してもらいたいです。

これは、他の人がアルゴリズムを説明するのを楽しんでいるように見える場所のようです: http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

「abba」などの文字列を #a#b#b#a# に変換したい理由は理解できます。たとえば、前述の Web サイトの作成者は、アルゴリズムの重要な部分は次のように述べています。

                      if P[ i' ] ≤ R – i,
                      then P[ i ] ← P[ i' ]
                      else P[ i ] ≥ P[ i' ]. (Which we have to expand past 
                      the right edge (R) to find P[ i ])

P[i'] = 7 で、P[i] が R - i 以下ではない場合、P[i] は 5 に等しいと彼/彼女はある時点で言っているので、これは間違っているようです。

アルゴリズムに慣れていない場合は、次のリンクを参照してください: http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html用語がひどくて紛らわしいです.まず、定義されていないものがあります.また、変数が多すぎます.どの変数が何を参照しているかを思い出すためのチェックリストが必要です.)

もう 1 つは: http://www.akalin.cx/longest-palindrome-linear-time (頑張ってください)

アルゴリズムの基本的な要点は、線形時間で最長の回文を見つけることです。最小から中程度の労力で O(n^2) で実行できます。このアルゴリズムは、O(n) に到達するために非常に「賢い」はずです。

4

10 に答える 10

39

リンクの説明の論理が正しくないことに同意します。以下に詳細を示します。

Manacherのアルゴリズムは、iを中心とする回文がどこまで伸びているかを含むテーブルP[i]に入力します。P [5] = 3の場合、位置5の両側にある3文字が回文の一部です。このアルゴリズムは、長いパリンドロームを見つけた場合、左側のPの値を確認することで、パリンドロームの右側のPの値をすばやく入力できるという事実を利用しています。同じ。

あなたが話していたケースを説明することから始め、次に必要に応じてこの答えを拡張します。

Rは、Cを中心とする回文の右側のインデックスを示します。指定した場所の状態は次のとおりです。

C=11
R=20
i=15
i'=7
P[i']=7
R-i=5

ロジックは次のようになります。

if P[i']<=R-i:  // not true
else: // P[i] is at least 5, but may be greater

リンクの擬似コードは、テストが失敗した場合、P[i]はP[i']以上である必要があることを示していますが、Ri以上である必要があると思います。説明は、それを裏付けています。

P [i']はRiより大きいため、i'を中心とする回文は、Cを中心とする回文を超えて拡張されます。iを中心とする回文は、その時点まで対称性があるため、少なくともRi文字幅になることがわかっています。しかし、それを超えて明示的に検索する必要があります。

P [i']がRiより大きくなかった場合、i'を中心とする最大の回文はCを中心とする最大の回文内にあるため、P[i]はP[i]より大きくなることはないことがわかります。 ']。もしそうなら、矛盾が生じるでしょう。これは、iを中心とする回文をP [i']を超えて拡張できることを意味しますが、可能であれば、対称性のためにi'を中心とする回文も拡張できますが、すでにできるだけ大きくする必要があります。

このケースは前に説明されています：

C=11
R=20
i=13
i'=9
P[i']=1
R-i=7

この場合、P [i']<=Riです。Cを中心とする回文の端からまだ7文字離れているので、iの周りの少なくとも7文字はi'の周りの7文字と同じであることがわかります。i'の周りには1文字の回文しかなかったので、iの周りにも1文字の回文があります。

j_random_hackerは、ロジックが次のようになる必要があることに気づきました。

if P[i']<R-i then
  P[i]=P[i']
else if P[i']>R-i then
  P[i]=R-i
else P[i]=R-i + expansion

P [i'] <Riの場合、Cを中心とする回文内にいるため、P [i] ==P[i']であることがわかります。

P [i']> Riの場合、P [i] == Riであることがわかります。そうしないと、Cを中心とする回文がRを超えて拡張してしまうためです。

したがって、拡張が実際に必要になるのは、P [i'] == Riの特別な場合のみです。したがって、P[i]の回文が長くなる可能性があるかどうかはわかりません。

これは、実際のコードでP [i] = min（P [i']、Ri）を設定し、常に展開することで処理されます。この方法では、拡張が必要な​​い場合、拡張にかかる時間は一定であるため、時間の複雑さは増しません。

于 2012-05-06T06:49:57.120 に答える
13

次のリンクで、これまでで最高の説明の1つを見つけました。

http://tarokuriyama.com/projects/palindrome2.php

また、質問で言及された最初のリンクで使用されているのと同じ文字列の例 (babcbabcbaccba) の視覚化もあります。

このリンクとは別に、コードも見つけました

http://algs4.cs.princeton.edu/53substring/Manacher.java.html

このアルゴリズムの要点を理解しようと懸命に努力している他の人に役立つことを願っています。

于 2013-12-24T19:52:39.283 に答える
12

このサイトのアルゴリズムはある程度理解できるようです http://www.akalin.cx/longest-palindrome-linear-time

この特定のアプローチを理解するには、紙の上で問題を解決し、可能性のある各センターの回文のチェックを回避するために実装できるトリックを見つけてください。

最初に自分自身に答えてください - 与えられた長さの回文を見つけたら、たとえば 5 としましょう - 次のステップとして、この回文の終わりにジャンプできませんか (4 つの文字と 4 つの中間文字をスキップします)。

長さ 8 の回文を作成し、長さ > 8 の別の回文を配置しようとすると、中心が最初の回文の右側にあることに気付くでしょう。試してみてください: 長さ 8 の回文 - WOWILIKEEKIL - Like + ekiL = 8 これで、ほとんどの場合、2 つの E の間の場所を中心として、数字の 8 を長さとして書き留め、最後の L の後にジャンプして探すことができます。大きな回文の中心。

このアプローチは正しくありません。より大きな回文の中心が ekiL の内側にある可能性があり、最後の L の後にジャンプすると、それを見逃すことになります。

LIKE+EKIL を見つけたら、これらのアルゴリズムが使用する配列に 8 を配置すると、次のようになります。

[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8]

為に

[#,W,#,O,#,W,#,I,#,L,#,I,#,K,#,E,#]

トリックは、8 の後の次の 7 (8-1) の数字が左側と同じになる可能性が最も高いことを既に知っているため、次のステップでは、7 の数字を 8 の左から 8 の右に自動的にコピーします。それらはまだ最終的なものではないことに注意してください。配列は次のようになります

[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8,1,0,1,0,1,0,3] (私たちは8時です）

為に

[#,W,#,O,#,W,#,I,#,L,#,I,#,K,#,E,#,E,#,K,#,I,#,L]

そのようなジャンプが現在のソリューションを破壊し、何がわかるかを見てみましょう。

WOWILIKEEKIL - EKIL 内のどこかに中心を持つ、より大きな回文を作成してみましょう。しかし、それは不可能です。単語 EKIL を回文を含むものに変更する必要があります。何？OOOOOh - それがトリックです。現在の回文の右側に中心を持つより大きな回文を持つ唯一の可能性は、それがすでに回文の右側 (および左側) にあるということです。

WOWILIKEEKIL に基づいたものを作成してみましょう。たとえば、EKIL を EKIK に変更し、I をより大きな回文の中心として使用する必要があります。LIKE も KIKE に変更することを忘れないでください。トリッキーな回文の最初の文字は次のようになります。

WOWIKIKEEKIK

前に述べたように - 最後の I を KIKEEKIK よりも大きな回文の中心にします。

WOWIKIKEEKIKEKIWW

古いパリンドロームまでの配列を作成し、追加情報を平均化する方法を見つけてみましょう。

為に

[_ W _ O _ W _ I _ K _ I _ K _ E _ E _ K _ I _ K _ E _ E _ K _ I _ K _ I _ W ]

[0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8

次の I - a 3rd が最長のパリンドロームになることはわかっていますが、それについては少し忘れましょう。配列内の数字を 8 の左から右にコピーします (8 つの数字)

[0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8,1,0,1,0,3,0,3]

私たちのループでは、番号 8 の E の間にあります。K (現在最大の回文の最後の文字) に直接ジャンプできない I (最大の回文の将来の真ん中) の特別な点は何ですか? 特別なことは、配列の現在のサイズを超えていることです...どのように? 3 つのスペースの右に 3 つのスペースを移動すると、配列から外れます。これは、最大の回文の真ん中であり、ジャンプできる最も遠いところがこの文字 I であることを意味します。

この回答が長くなって申し訳ありません-アルゴリズムを説明したかったので、あなたを保証できます-@OmnipotentEntityは正しかった-あなたに説明した後、私はそれをさらによく理解しています:)

于 2013-02-18T00:43:46.427 に答える
0 
class Palindrome
{
    private int center;
    private int radius;

    public Palindrome(int center, int radius)
    {
        if (radius < 0 || radius > center)
            throw new Exception("Invalid palindrome.");

        this.center = center;
        this.radius = radius;
    }

    public int GetMirror(int index)
    {
        int i = 2 * center - index;

        if (i < 0)
            return 0;

        return i;
    }

    public int GetCenter()
    {
        return center;
    }

    public int GetLength()
    {
        return 2 * radius;
    }

    public int GetRight()
    {
        return center + radius;
    }

    public int GetLeft()
    {
        return center - radius;
    }

    public void Expand()
    {
        ++radius;
    }

    public bool LargerThan(Palindrome other)
    {
        if (other == null)
            return false;

        return (radius > other.radius);
    }

}

private static string GetFormatted(string original)
{
    if (original == null)
        return null;
    else if (original.Length == 0)
        return "";

    StringBuilder builder = new StringBuilder("#");
    foreach (char c in original)
    {
        builder.Append(c);
        builder.Append('#');
    }

    return builder.ToString();
}

private static string GetUnFormatted(string formatted)
{
    if (formatted == null)
        return null;
    else if (formatted.Length == 0)
        return "";

    StringBuilder builder = new StringBuilder();
    foreach (char c in formatted)
    {
        if (c != '#')
            builder.Append(c);
    }

    return builder.ToString();
}

public static string FindLargestPalindrome(string str)
{
    string formatted = GetFormatted(str);

    if (formatted == null || formatted.Length == 0)
        return formatted;

    int[] radius = new int[formatted.Length];

    try
    {
        Palindrome current = new Palindrome(0, 0);
        for (int i = 0; i < formatted.Length; ++i)
        {
            radius[i] = (current.GetRight() > i) ?
                Math.Min(current.GetRight() - i, radius[current.GetMirror(i)]) : 0;

            current = new Palindrome(i, radius[i]);

            while (current.GetLeft() - 1 >= 0 && current.GetRight() + 1 < formatted.Length &&
                formatted[current.GetLeft() - 1] == formatted[current.GetRight() + 1])
            {
                current.Expand();
                ++radius[i];
            }
        }

        Palindrome largest = new Palindrome(0, 0);
        for (int i = 0; i < radius.Length; ++i)
        {
            current = new Palindrome(i, radius[i]);
            if (current.LargerThan(largest))
                largest = current;
        }

        return GetUnFormatted(formatted.Substring(largest.GetLeft(), largest.GetLength()));
    }
    catch (Exception ex) 
    {
        Console.WriteLine(ex);
    }

    return null;
}
于 2013-09-30T06:37:21.063 に答える