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

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

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

Première réponse vous-même - lorsque vous trouvez un palindrome de longueur donnée, disons 5 - ne pouvez-vous pas comme étape suivante, sautez à la fin de cette palindrome (sauter 4 lettres et 4 Mi-lettres)?

Si vous essayez de créer un palindrome de longueur 8 et placez un autre palindrome de longueur > 8, dont le centre se trouve dans le côté droit du premier palindrome, vous remarquerez quelque chose de drôle. L'essayer: Palindrome avec longueur 8-Wowilikeekil-Like + ekiL = 8 Maintenant dans la plupart des cas vous seriez en mesure d'écrire l'endroit entre deux E comme un centre et le nombre 8 comme la longueur et sauter après le dernier L pour chercher le centre du plus grand palindrome.

Cette approche n'est pas correcte, le centre du palindrome plus grand peut être à l'intérieur d'ekiL et vous le manqueriez si vous sautiez après le dernier L.

Après avoir trouvé LIKE + EKIL, vous placez 8 dans le tableau que ces algos utilisent et cela ressemble à:

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

Pour

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

L'astuce est que vous savez déjà que très probablement les 7 (8-1) numéros suivants après 8 seront les mêmes que sur le côté gauche, donc l'étape suivante consiste à copier automatiquement 7 numéros de gauche de 8 à droite de 8 en gardant à l'esprit qu'ils ne sont pas encore définitifs. Le tableau ressemblerait à ceci

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

Pour

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

Faisons un exemple, qu'un tel saut détruirait notre solution actuelle et verrait ce que nous pouvons remarquer.

WOWILIKEEKIL-permet d'essayer de faire un plus grand palindrome avec le centre quelque part dans EKIL. Mais ce n'est pas possible - nous devons changer le mot EKIL en quelque chose qui contient du palindrome. Comment? OOOOOh-c'est l'astuce. La seule possibilité d'avoir un plus grand palindrome avec le centre dans le côté droit de notre palindrome actuel est qu'il est déjà dans le côté droit (et gauche) du palindrome.

Essayons d'en construire un basé sur WOWILIKEEKIL Nous devrions changer EKIL pour par exemple EKIK avec I comme centre du plus grand palindrome-n'oubliez pas de changer comme KIKE aussi bien. Les premières lettres de notre palindrome délicat seront:

WOWIKIKEEKIK

Comme dit précédemment-que le dernier i soit le centre du pallindrome plus grand que KIKEEKIK:

WOWIKIKEEKIKEEKIKIW

Faisons le tableau jusqu'à notre vieux pallindrom et découvrons comment laver les informations supplémentaires.

Pour

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

Ce sera [0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8

Nous savons que le prochain i-a 3rd sera le pallindrome le plus long, mais oublions-le un peu. permet de copier les nombres dans le tableau de la gauche de 8 vers la droite (8 nombres)

[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 les E avec le numéro 8. Quelle est la particularité de I (futur milieu du plus grand pallindrome) que nous ne pouvons pas sauter directement à K (La dernière lettre du plus grand pallindrome actuellement)? Le la chose spéciale est qu'il dépasse la taille actuelle du tableau ... comment? Si vous déplacez 3 espaces à droite de 3-vous êtes hors du tableau. Cela signifie qu'il peut être au milieu du plus grand pallindrome et le plus éloigné que vous pouvez sauter est cette lettre I.

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

J'ai trouvé l'une des meilleures explications jusqu'à présent sur le lien suivant:

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

Il a également une visualisation pour le même exemple de chaîne (babcbabcbaccba) utilisé au premier lien mentionné dans la question.

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

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

J'espère que cela sera utile aux autres qui essaient de comprendre le nœud de cet algorithme.

Article Complet: http://www.zrzahid.com/longest-palindromic-substring-in-linear-time-manachers-algorithm/

Tout D'abord permet d'observer de près un palindrome afin de trouver des propriétés intéressantes. Par exemple, S1 = "abaaba" et S2 = "abcba", les deux sont palindrome mais quelle est la différence non triviale (c'est-à-dire pas de longueur ou de caractères) entre eux? S1 est un palindrome centré autour de l'espace invisible entre i = 2 et i = 3 (Espace inexistant!). D'autre part S2 est centré autour du caractère à i=2 (ie. C). Afin de gérer gracieusement le centre d'un palindrome quelle que soit la longueur impaire/paire, transformons le palindrome en insérant un caractère spécial $ entre les caractères. Alors S1="abba" et S2="abcba" sera transformé en T1="$a$b$a$a$b$a$", centré à i=6 et T2="$a$b$c$b$a$", centré à i=5. Maintenant, nous pouvons voir que les centres sont existants et les longueurs sont cohérentes 2 * n + 1, Où n = longueur de la chaîne d'origine. Exemple,

                    i'          c           i           
      -----------------------------------------------------
      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
      ----------------------------------------------------- 
   T1=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
      -----------------------------------------------------

Ensuite, observez qu'à partir de la propriété symétrique d'un palindrome (transformé) t autour du Centre c, T[c-k] = T[c+k] pour 0 i' = 2 * c-i et vice versa. C'est,

Pour chaque position i à droite du centre c d'une sous-chaîne palindromique, la position miroir de i est, i' = 2 * c-i, et inversement.

Définissons un tableau P [0..2 * N] tel que P[i] est égal à la longueur du palindrome centré sur I. notez que, la longueur est réellement mesurée par le nombre de caractères dans la chaîne d'origine (en ignorant les caractères spéciaux $). Soit aussi min et max respectivement la limite la plus à gauche et la limite la plus à droite d'une sous-chaîne palindromique centrée à C. Donc, min=c-P[c] et max=C + P[c]. Par exemple, pour palindrome S= "abaaba", le palindrome transformé T, centre de miroir c = 6, Tableau de longueur P [0..12], min=c-P[c]=6-6=0, max=c+P[c]=6+6=12 et deux de l'échantillon miroir indices i et i' sont présentés dans la figure suivante.

      min           i'          c           i           max
      -----------------------------------------------------
      | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12|
      ----------------------------------------------------- 
    T=| $ | a | $ | b | $ | a | $ | a | $ | b | $ | a | $ |
      -----------------------------------------------------
    P=| 0 | 1 | 0 | 3 | 0 | 5 | 6 | 1 | 0 | 3 | 0 | 1 | 0 |
      -----------------------------------------------------

Avec un tel tableau de longueur P, nous pouvons trouver la longueur de la plus longue sous-chaîne palindromique en regardant dans L'élément max de P. c'est-à-dire

P [i] est la longueur d'une sous-chaîne palindromique avec le centre à i dans la chaîne transformée T, ie. centre à i/2 dans la chaîne s d'origine; par conséquent, la plus longue sous-chaîne palindromique serait la sous-chaîne de length P[i_max] à partir de l'indice (i_max-P[i_max])/2 tel que i_max est l'indice de l'élément maximal de P.

Dessinons une figure similaire dans la suite pour notre exemple non palindromique string s = "babaabca".

                       min              c               max
                       |----------------|-----------------|
      --------------------------------------------------------------------
 idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
      --------------------------------------------------------------------- 
    T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
      ---------------------------------------------------------------------
    P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
      ---------------------------------------------------------------------

La Question Est de savoir comment calculer P efficacement. La propriété symétrique suggère les cas suivants que nous pourrions potentiellement utiliser pour calculer P [i] en utilisant P[i'] précédemment calculé à l'index miroir i' sur la gauche, d'où sauter beaucoup de calculs. Supposons que nous ayons un palindrome de référence (premier palindrome) pour commencer.

1. Un troisième palindrome dont le centre est dans le côté droit d'un premier palindrome aura exactement la même longueur que celle d'un second palindrome ancré au centre du miroir sur le côté gauche, si le second palindrome est dans les limites du premier palindrome par au moins un caractère.

   Par exemple dans la figure suivante avec le premier palindrome centré à c = 8 et délimité par min = 4 et max = 12, longueur du troisième palindrome centré à i = 9 (avec indice miroir i'= 2*c-i = 7) est, P [i] = P [i'] = 1. C'est parce que le deuxième palindrome centré à i' est dans les limites du premier palindrome. De Même, P [10] = P [6] = 0.

   
   
                                         |----3rd----|
                                 |----2nd----|        
                          |-----------1st Palindrome---------|
                          min          i'  c   i           max
                          |------------|---|---|-------------|
         --------------------------------------------------------------------
    idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
         --------------------------------------------------------------------- 
       T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
         ---------------------------------------------------------------------
       P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | ? | ? | ? | ? | ? | ? | ? | ? |
         ---------------------------------------------------------------------
   

   Maintenant, la question est de savoir comment vérifier ce cas? Notez que, en raison de la propriété symétrique longueur du segment [min..i'] est égal à la longueur du segment [I..Max]. Notez également que le 2ème palindrome est complètement à l'intérieur 1er palindrome IFF bord gauche du 2ème palindrome est à l'intérieur de la limite gauche, min du 1er palindrome. C'est,

   
           i'-P[i'] >= min
           =>P[i']-i' &lt -min (negate)
           =>P[i'] &lt i'-min 
           =>P[i'] &lt max-i [(max-i)=(i'-min) due to symmetric property].
   

   Combiner tous les faits dans le cas 1,

   P[i] = P[i'], iff (max-i) > P[i']

2. Si le second palindrome rencontre ou s'étend au-delà de la limite gauche du premier palindrome, alors le troisième palindrome est garanti d'avoir au moins la longueur de son propre centre au caractère le plus externe droit du premier palindrome. Cette longueur est la même de le centre du second palindrome au caractère le plus à gauche du premier palindrome.

   Par exemple dans la figure suivante, le second palindrome centré à i=5 s'étend au-delà de la limite gauche du premier palindrome. Donc, dans ce cas, nous ne pouvons pas dire P [i] = P [i']. Mais la longueur du troisième palindrome centré à i = 11, P [i] est au moins la longueur de son centre i = 11 à la limite droite max = 12 du premier palindrome centré à C. C'est-à-dire, P [i] > = 1. Cela signifie que le troisième palindrome pourrait être étendu passé max si et seulement si prochain caractère immédiat passé max correspond exactement avec le caractère en miroir, et nous continuons cette vérification au-delà. Par exemple, dans ce cas P[13]!= P [9] et il ne peut pas être étendu. Donc, P [i] = 1.

                                                       
                 |-------2nd palindrome------|   |----3rd----|---?    
                          |-----------1st Palindrome---------|
                          min  i'          c           i   max
                          |----|-----------|-----------|-----|
         --------------------------------------------------------------------
    idx= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| 16|
         --------------------------------------------------------------------- 
       T=| $ | b | $ | a | $ | b | $ | a | $ | a | $ | b | $ | c | $ | a | $ |
         ---------------------------------------------------------------------
       P=| 0 | 1 | 0 | 3 | 0 | 3 | 0 | 1 | 4 | 1 | 0 | ? | ? | ? | ? | ? | ? |
         ---------------------------------------------------------------------
   

   Donc, comment faire pour vérifier ce cas? C'est simplement la vérification échouée pour le cas 1. C'est-à-dire que le deuxième palindrome s'étendra au-delà du bord gauche du premier palindrome iff,

   
           i'-P[i'] &lt min
           =>P[i']-i' >= -min [negate]
           =>P[i'] >= i'-min 
           =>P[i'] >= max-i [(max-i)=(i'-min) due to symmetric property]. 
   

   C'est, P[i] est au moins (max-i) ssi (max-i) P[i]>=(max-i), le forum (max-je) Maintenant, si le troisième palindrome s'étend au-delà de max, nous devons mettre à jour le centre et la limite du nouveau palindrome.

   Si le palindrome centré sur i s'étend au-delà de max, nous avons un nouveau palindrome (étendu), d'où un nouveau centre à c=I. mettez à jour max à la limite la plus à droite du nouveau palindrome.

   En combinant tous les faits dans le cas 1 et le cas 2, nous pouvons arriver à une très belle petite formule:

   
           Case 1: P[i] = P[i'],  iff (max-i) > P[i']
           Case 2: P[i]>=(max-i), iff (max-i) = min(P[i'], max-i). 
   

   C'est-à-dire, P[i]=min(P[i'], max-I) lorsque le troisième palindrome n'est pas extensible après max. Sinon, nous avons troisième palindrome au centre c=i et nouveau max=i+P[i].

3. Ni le premier ni le deuxième palindrome ne fournissent d'informations pour aider à déterminer la longueur palindromique d'un quatrième palindrome dont le centre est à l'extérieur du côté droit du premier palindrome.

   Autrement dit, Nous ne pouvons pas déterminer de manière préventive P [i] si i > max. C'est,

   P [i] = 0, IFF max-i &LT 0

   En combinant tous les cas, nous concluons les formules:

   P[i] = max> - je ? min (P [i'], max-i): 0. Au cas où nous le pourrions développer au-delà de max ensuite, nous développons en faisant correspondre les caractères au-delà de max avec le caractère en miroir par rapport au nouveau centre à c = I. enfin, lorsque nous avons une discordance, nous mettons à jour new max=i+P[i].

Référence: description de l'algorithme dans la page wiki

J'ai fait une vidéo sur cet algorithme en utilisant des graphiques D'Animation. Espérons que cela vous aidera à le comprendre! https://www.youtube.com/watch?v=kbUiR5YWUpQ

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

Ce matériel est d'une grande aide pour moi de le comprendre: http://solutionleetcode.blogspot.com/2013/07/leetcode-longest-palindromic-substring.html

Définissez T comme la longueur des sous-chaînes palindromiques les plus longues centrées sur chacun des caractères.

L'essentiel est que lorsque des palindromes plus petits sont complètement intégrés dans le palindrome plus long, T [i] devrait également être symétrique dans le palindrome plus long.

Sinon, nous devrons calculer T[i] à partir de scratch, plutôt que d'induire à partir de la partie gauche symétrique.

using namespace std;

class Palindrome{
public:
    Palindrome(string st){
        s = st; 
        longest = 0; 
        maxDist = 0;
        //ascii: 126(~) - 32 (space) = 94 
        // for 'a' to 'z': vector<vector<int>> v(26,vector<int>(0)); 
        vector<vector<int>> v(94,vector<int>(0)); //all ascii 
        mDist.clear();
        vPos = v; 
        bDebug = true;
    };

    string s;
    string sPrev;    //previous char
    int longest;     //longest palindrome size
    string sLongest; //longest palindrome found so far
    int maxDist;     //max distance been checked 
    bool bDebug;

    void findLongestPal();
    int checkIfAnchor(int iChar, int &i);
    void checkDist(int iChar, int i);

    //store char positions in s pos[0] : 'a'... pos[25] : 'z' 
    //       0123456
    // i.e. "axzebca" vPos[0][0]=0  (1st. position of 'a'), vPos[0][1]=6 (2nd pos. of 'a'), 
    //                vPos[25][0]=2 (1st. pos. of 'z').  
    vector<vector<int>> vPos;

    //<anchor,distance to check> 
    //   i.e.  abccba  anchor = 3: position of 2nd 'c', dist = 3 
    //   looking if next char has a dist. of 3 from previous one 
    //   i.e.  abcxcba anchor = 4: position of 2nd 'c', dist = 4 
    map<int,int> mDist;
};

//check if current char can be an anchor, if so return next distance to check (3 or 4)
// i.e. "abcdc" 2nd 'c' is anchor for sub-palindrome "cdc" distance = 4 if next char is 'b'
//      "abcdd: 2nd 'd' is anchor for sub-palindrome "dd"  distance = 3 if next char is 'c'
int Palindrome::checkIfAnchor(int iChar, int &i){
    if (bDebug)
          cout<<"checkIfAnchor. i:"<<i<<" iChar:"<<iChar<<endl;
    int n = s.size();
    int iDist = 3;
    int iSize = vPos[iChar].size();
    //if empty or distance to closest same char > 2
    if ( iSize == 0 || vPos[iChar][iSize - 1] < (i - 2)){
        if (bDebug)
              cout<<"       .This cannot be an anchor! i:"<<i<<" : iChar:"<<iChar<<endl; 
        //store char position
        vPos[iChar].push_back(i);
        return -1; 
    }

    //store char position of anchor for case "cdc"
    vPos[iChar].push_back(i);    
    if (vPos[iChar][iSize - 1] == (i - 2))
        iDist = 4;
    //for case "dd" check if there are more repeated chars
    else {
        int iRepeated = 0;
        while ((i+1) < n && s[i+1] == s[i]){
            i++;
            iRepeated++;
            iDist++; 
            //store char position
            vPos[iChar].push_back(i);
        }
    }

    if (bDebug)
          cout<<"       .iDist:"<<iDist<<" i:"<<i<<endl; 

    return iDist;
};

//check distance from previous same char, and update sLongest
void Palindrome::checkDist(int iChar, int i){
    if (bDebug)
            cout<<"CheckDist. i:"<<i<<" iChar:"<<iChar<<endl;
    int iDist;
    int iSize = vPos[iChar].size();
    bool b1stOrLastCharInString; 
    bool bDiffDist;

    //checkAnchor will add this char position 
    if ( iSize == 0){
        if (bDebug)
            cout<<"       .1st time we see this char. Assign it INT_MAX Dist"<<endl; 
        iDist = INT_MAX;
    }
    else {
        iDist = i - vPos[iChar][iSize - 1]; 
    }

    //check for distances being check, update them if found or calculate lengths if not.
    if (mDist.size() == 0) {
        if (bDebug)
             cout<<"       .no distances to check are registered, yet"<<endl;
        return;
    }

    int i2ndMaxDist = 0;
    for(auto it = mDist.begin(); it != mDist.end();){
        if (bDebug)
                cout<<"       .mDist. anchor:"<<it->first<<" . dist:"<<it->second<<endl; 
        b1stOrLastCharInString = false; 
        bDiffDist = it->second == iDist;  //check here, because it can be updated in 1st. if
        if (bDiffDist){
            if (bDebug)
                cout<<"       .Distance checked! :"<<iDist<<endl;
            //check if it's the first char in the string
            if (vPos[iChar][iSize - 1] == 0 || i == (s.size() - 1))
                b1stOrLastCharInString = true;
            //we will continue checking for more...
            else {
                it->second += 2; //update next distance to check
                if (it->second > maxDist) {
                     if (bDebug)
                          cout<<"       .previous MaxDist:"<<maxDist<<endl;
                     maxDist = it->second;
                     if (bDebug)
                          cout<<"       .new MaxDist:"<<maxDist<<endl;
                }
                else if (it->second > i2ndMaxDist) {//check this...hmtest
                     i2ndMaxDist = it->second;
                     if (bDebug)
                          cout<<"       .second MaxDist:"<<i2ndMaxDist<<endl;
                }
                it++; 
            }
        }
        if (!bDiffDist || b1stOrLastCharInString) {
            if (bDebug && it->second != iDist)
                cout<<"       .Dist diff. Anchor:"<<it->first<<" dist:"<<it->second<<" iDist:"<<iDist<<endl;
            else if (bDebug) 
                cout<<"       .Palindrome found at the beggining or end of the string"<<endl;

            //if we find a closest same char.
            if (!b1stOrLastCharInString && it->second > iDist){
                if (iSize > 1) {
                   if (bDebug)
                       cout<<"       . < Dist . looking further..."<<endl; 
                   iSize--;  
                   iDist = i - vPos[iChar][iSize - 1];
                   continue;    
                }
            }
            if (iDist == maxDist) {
                maxDist = 0;
                if (bDebug)
                     cout<<"       .Diff. clearing Max Dist"<<endl;
            }
            else if (iDist == i2ndMaxDist) {
                i2ndMaxDist = 0;
                if (bDebug)
                      cout<<"       .clearing 2nd Max Dist"<<endl; 
            }

            int iStart; 
            int iCurrLength;
            //first char in string
            if ( b1stOrLastCharInString && vPos[iChar].size() > 0 && vPos[iChar][iSize - 1] == 0){
                iStart = 0;
                iCurrLength = i+1;
            }
            //last char in string
            else if (b1stOrLastCharInString && i == (s.size() - 1)){
                iStart = i - it->second; 
                iCurrLength = it->second + 1;
            }
            else {
                iStart = i - it->second + 1; 
                iCurrLength = it->second - 1;  //"xabay" anchor:2nd. 'a'. Dist from 'y' to 'x':4. length 'aba':3
            }

            if (iCurrLength > longest){
                if (bDebug)
                      cout<<"       .previous Longest!:"<<sLongest<<" length:"<<longest<<endl;
                longest = iCurrLength;               
                sLongest = s.substr(iStart, iCurrLength);

                if (bDebug)
                      cout<<"       .new Longest!:"<<sLongest<<" length:"<<longest<<endl;
            }

            if (bDebug)
                  cout<<"       .deleting iterator for anchor:"<<it->first<<" dist:"<<it->second<<endl; 

            mDist.erase(it++);
        }
    }


    //check if we need to get new max distance
    if (maxDist == 0 && mDist.size() > 0){ 
        if (bDebug)
              cout<<"       .new maxDist needed";
        if (i2ndMaxDist > 0) {
            maxDist = i2ndMaxDist;
            if (bDebug)
              cout<<"       .assigned 2nd. max Dist to max Dist"<<endl;
        }
        else {
            for(auto it = mDist.begin(); it != mDist.end(); it++){
                if (it->second > maxDist)
                    maxDist = it->second;
            }
            if (bDebug)
              cout<<"       .new max dist assigned:"<<maxDist<<endl;
        }
    }  
};        

void Palindrome::findLongestPal(){
    int n = s.length(); 
    if (bDebug){
        cout<<"01234567891123456789212345"<<endl<<"abcdefghijklmnopqrstuvwxyz"<<endl<<endl;            
        for (int i = 0; i < n;i++){
            if (i%10 == 0)
                cout<<i/10;
            else
                cout<<i;
        }
        cout<<endl<<s<<endl;
    }
    if (n == 0)
        return;

    //process 1st char
    int j = 0;
    //for 'a' to 'z' : while (j < n && (s[j] < 'a' && s[j] > 'z'))
    while (j < n && (s[j] < ' ' && s[j] > '~'))
        j++;
    if (j > 0){
        s.substr(j);
        n = s.length();
    }
    // for 'a' to 'z' change size of vector from 94 to 26 : int iChar = s[0] - 'a';
    int iChar = s[0] - ' ';
    //store char position
    vPos[iChar].push_back(0);  

    for (int i = 1; i < n; i++){
        if (bDebug)
            cout<<"findLongestPal. i:"<<i<<" "<<s.substr(0,i+1)<<endl; 
        //if max. possible palindrome would be smaller or equal 
        //             than largest palindrome found then exit
        //   (n - i) = string length to check 
        //   maxDist: max distance to check from i 
        int iPossibleLongestSize = maxDist + (2 * (n - i));
        if ( iPossibleLongestSize <= longest){
            if (bDebug)
                cout<<"       .PosSize:"<<iPossibleLongestSize<<" longest found:"<<iPossibleLongestSize<<endl;
            return;
        }

        //for 'a' to 'z' : int iChar = s[i] - 'a';
        int iChar = s[i] - ' ';
        //for 'a' to 'z': if (iChar < 0 || iChar > 25){
        if (iChar < 0 || iChar > 94){
            if (bDebug)
                cout<<"       . i:"<<i<<" iChar:"<<s[i]<<" skipped!"<<endl;
            continue;
        }

        //check distance to previous char, if exist
        checkDist(iChar, i);

        //check if this can be an anchor
        int iDist = checkIfAnchor(iChar,i);
        if (iDist == -1) 
            continue;

        //append distance to check for next char.
        if (bDebug)
                cout<<"       . Adding anchor for i:"<<i<<" dist:"<<iDist<<endl;
        mDist.insert(make_pair(i,iDist));

        //check if this is the only palindrome, at the end
        //i.e. "......baa" or "....baca" 
        if (i == (s.length() - 1) && s.length() > (iDist - 2)){
            //if this is the longest palindrome! 
            if (longest < (iDist - 1)){
                sLongest = s.substr((i - iDist + 2),(iDist - 1));
            }
        }
    }
};

int main(){
    string s;
    cin >> s;

    Palindrome p(s);
    p.findLongestPal();
    cout<<p.sLongest; 
    return 0;
}