Algorithme de Manacher (algorithme pour trouver la plus longue sous-chaîne palindrome en temps linéaire)

Question

Après avoir passé environ 6 à 8 heures à essayer de digérer le Manacher de l'algorithme, je suis prêt à jeter l'éponge. Mais avant que je le fais, voici un dernier coup dans le noir: peut-on l'expliquer? Je n'ai pas de soins sur le code. Je veux quelqu'un pour expliquer l' ALGORITHME.

Ici semble être un endroit que les autres, semblait jouir dans l'explication de l'algorithme: http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

Je comprends pourquoi vous voulez transformer la chaîne, disons, 'abba' #a#b#b#a# Après que je suis perdu. Par exemple, l'auteur du site web précédemment mentionné dit la partie clé de l'algorithme est:

                      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 ])

Cela semble mal, parce qu'il/elle dit à un moment que P[i] est égal à 5 lors de la P[i'] = 7 et P[i] n'est pas inférieur ou égal à R - je.

Si vous n'êtes pas familier avec l'algorithme, voici quelques liens: http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (j'ai essayé celui-ci, mais la terminologie est terrible et déroutant. Tout d'abord, certaines choses ne sont pas définis. Aussi, trop de variables. Vous avez besoin d'une liste de contrôle de rappeler ce que la variable se réfère à ce.)

Un autre est: http://www.akalin.cx/longest-palindrome-linear-time (bonne chance)

Le sens de base de l'algorithme est de trouver le plus long palindrome dans le temps linéaire. Il peut être fait en O(n^2) avec un minimum de moyen montant de l'effort. Cet algorithme est censé être assez "intelligent" pour le faire descendre à O(n).

Answer 1

Je suis d'accord que la logique n'est pas tout à fait droit dans l'explication du lien. Je donne quelques détails ci-dessous.

Manacher de l'algorithme remplit un tableau P[i] qui contient dans quelle mesure le palindrome centrée au i s'étend. Si P[5]=3, puis trois caractères sur chaque côté de la position de cinq font partie du palindrome. L'algorithme repose sur le fait que si vous avez trouvé un long palindrome, vous pouvez spécifier les valeurs de P sur le côté droit de l'palindrome rapidement en regardant les valeurs de P sur le côté gauche, car ils doivent surtout être le même.

Je vais commencer par expliquer le cas où vous étiez en train de parler, et puis je vais développer cette réponse au besoin.

R indique l'index du côté droit de l'palindrome centrée au C. Voici l'état à l'endroit que vous avez indiqué:

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

et la logique est comme ceci:

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

Le pseudo-code dans le lien indique que P[i] doit être supérieur ou égal à P[i'] si le test échoue, mais je pense qu'elle doit être supérieure ou égale à R-i, et l'explication dos.

Puisque P[i'] est plus grand que R-i, le palindrome, centré à i' s'étend au-delà du palindrome centrée au C. Nous savons que le palindrome centrée au je vais être d'au moins R-i caractères de large, parce que nous avons encore la symétrie jusqu'à ce point, mais nous devons rechercher explicitement au-delà.

Si P[i'] a pas été supérieure à R-i, alors le plus grand palindrome centrée au i "est dans le plus grand palindrome centré en C, afin que nous ayons connu que P[i] ne pouvait pas être plus importante que P[i']. S'il l'était, on aurait une contradiction. Cela voudrait dire que nous serions en mesure d'étendre le palindrome centrée au i au-delà de P[i'], mais si nous pouvions, nous aussi être en mesure d'étendre le palindrome centrée au i " en raison de la symétrie, mais il était déjà censé être aussi grande que possible.

Ce cas est illustré précédemment:

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

Dans ce cas, P[i']<=R-je. Puisque nous sommes encore 7 caractères à partir du bord de la palindrome centré en C, nous savons qu'au moins 7 caractères autour de moi, je sont les mêmes que les 7 personnages autour de moi, je'. Car il n'y avait qu'un caractère palindrome autour de moi, je", il est d'un caractère palindrome autour de moi, je.

j_random_hacker remarqué que la logique devrait être plus comme ceci:

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

Si P[i'] < R-i, alors nous savons que P[i]==P[i'], puisque nous sommes encore à l'intérieur du palindrome centrée au C.

Si P[i'] > R-i, alors nous savons que P[i]==R-i, parce que sinon, le palindrome centrée au C aurait prolongé au-delà de R.

L'expansion est vraiment nécessaire que dans le cas particulier où P[i']==R-i, de sorte que nous ne savons pas si le palindrome P[i] peut-être plus.

Il est géré dans le code par le paramètre P[i]=min(P[i'],R-i) et puis toujours en expansion. Cette façon de faire, elle n'augmente pas la complexité du temps, parce que si aucune extension n'est nécessaire, le temps nécessaire pour faire l'expansion constante.

Answer 2

J'ai trouvé l'un de la meilleure explication jusqu'à présent sur le lien suivant:

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

Il dispose également d'un système de visualisation pour le même exemple de chaîne (babcbabcbaccba) utilisés sur le premier lien mentionné dans la question.

En dehors de ce lien, j'ai aussi trouvé le code à

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

J'espère que cela sera utile à d'autres à tenter de comprendre l'essentiel de cet algorithme.

Answer 3

L'algorithme sur ce site, semble compréhensible à un certain point http://www.akalin.cx/longest-palindrome-linear-time

Pour comprendre cette approche, le mieux est d'essayer de résoudre le problème sur le papier et attraper les trucs que vous pouvez mettre en œuvre pour éviter de vérifier le pallindrom pour chaque centre.

Première réponse de vous - même lorsque vous trouvez un pallindrome d'une longueur donnée, disons 5 - ne pouvez-vous pas comme étape suivante, sautez à la fin de cette pallindrome (en ignorant les 4 lettres et 4 midletters)?

Si vous essayez de créer un pallindrom avec une longueur de 8 et placer une autre pallindrome avec une longueur > 8, dont le centre est à droite de la première pallindrome vous remarquerez quelque chose de drôle. Essayez: Pallindrome avec une longueur de 8 WOWILIKEEKIL - Comme + ekiL = 8 Maintenant, dans la plupart des cas, vous pourriez être en mesure d'écrire en bas de la place entre les deux " E " en tant que centre et nombre 8, comme la longueur et le saut après le dernier L de regarder pour le centre de la plus grande pallindrome.

Cette approche n'est pas correcte, le centre de la plus grande pallindrome peut être à l'intérieur ekiL et vous manquer si vous voulez sauter après le dernier L.

Une fois que vous trouvez COMME+EKIL vous placer 8 dans le tableau que ces algos utiliser et cela ressemble à:

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

pour

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

Le truc, c'est que vous savez déjà que la plupart probablement le prochain 7 (8-1) chiffres après 8 sera la même que sur le côté gauche, de sorte que la prochaine étape est de copier automatiquement des 7 numéros de la gauche de 8 de 8 en gardant à l'esprit qu'ils ne sont pas encore définitifs. Le tableau devrait ressembler à ceci

[0,1,0,3,0,1,0,1,0,3,0,1,0,1,0,1,8,1,0,1,0,1,0,3] (nous en sommes à 8)

pour

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

Nous allons faire un exemple, qu'un tel saut détruire notre solution actuelle et de voir ce que nous pouvons avis.

WOWILIKEEKIL - permet d'essayer de faire de plus grands pallindrome avec le centre de quelque part à l'intérieur de EKIL. Mais ce n'est pas possible - nous avons besoin de changer de mot EKIL à quelque chose qui contiennent pallindrome. Quoi? OOOOOh, c'est le truc. La seule possibilité d'avoir un plus grand pallindrome avec le centre dans le côté droit de notre pallindrome est qu'il est déjà dans la droite (et à gauche) à côté de pallindrome.

Nous allons essayer de construire une base sur WOWILIKEEKIL Nous aurions besoin de changer EKIL, par exemple, EKIK avec je comme un centre de la plus grande pallindrom - n'oubliez pas de changement de KIKE. Les premières lettres de notre délicate pallindrom sera:

WOWIKIKEEKIK

comme l'a dit avant de laisser le dernier que j'ai être le centre de la plus grande pallindrome que KIKEEKIK:

WOWIKIKEEKIKEEKIKIW

faisons le tableau jusqu'à nos vieux pallindrom et découvrez comment laverage les informations supplémentaires.

pour

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

il sera [0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8

nous savons que la prochaine je - un 3ème sera la plus longue pallindrome, mais oublions un peu. vous permet de copier des numéros dans le tableau à partir de la gauche de 8 à droite (8 numéros)

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

Dans notre boucle, nous sommes entre " E " avec le numéro 8. Ce qui est spécial à propos de I (futur milieu de la plus grande pallindrome) que nous ne pouvons pas sauter à droite de K (la dernière lettre de actuellement plus pallindrome)? Le truc, c'est qu'il dépasse la taille actuelle du tableau ... comment? Si vous déplacer de 3 cases vers la droite de la 3 - vous êtes hors de la matrice. Cela signifie qu'il peut être le milieu de la plus grande pallindrome et le plus loin vous pouvez sauter est cette lettre I.

Désolé pour la longueur de cette réponse - je voulais expliquer l'algorithme et peuvent s'assurer vous - @OmnipotentEntity avait raison - je le comprends encore mieux après avoir expliqué à vous :)

Answer 4

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;
}