Ответ 1

Я согласен с тем, что логика не совсем правильна в объяснении ссылки. Ниже приводятся некоторые подробности.

Алгоритм Manacher заполняет таблицу P [i], которая содержит, как далеко продвигается палиндром с центром в i. Если P [5] = 3, то три символа с каждой стороны позиции 5 являются частью палиндрома. Алгоритм использует тот факт, что если вы нашли длинный палиндром, вы можете быстро добавить значения 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. Мы знаем, что палиндром с центром в я будет по крайней мере Ri-символами, потому что у нас все еще есть симметрия до это точка, но мы должны искать явно выше этого.

Если P [i '] не превосходит Ri, то наибольший палиндром с центром в i' находится в самом большом палиндром с центром в C, поэтому мы знали бы, что P [i] не может быть больше Пи']. Если бы это было так, у нас было бы противоречие. Это означало бы, что мы могли бы расширить палиндром с центром в я за пределы P [i '], но если бы мы могли, то мы также смогли бы расширить палиндром с центром в i' из-за симметрии, но он уже был должен быть как можно большим.

Этот случай проиллюстрирован ранее:

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

В этом случае P [i '] <= R-i. Поскольку мы все еще находимся на расстоянии 7 символов от края палиндром с центром в C, мы знаем, что по крайней мере 7 символов вокруг я совпадают с 7 символами вокруг я '. Поскольку вокруг я был только один палиндром одного символа, есть и палиндром одного символа вокруг i.

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 '] < R-i, то мы знаем, что P [i] == P [i '], так как мы все еще находимся внутри палиндрома с центром в C.

Если P [i '] > R-i, то мы знаем, что P [i] == R-i, так как в противном случае палиндром, центрированный на C, продлил бы мимо R.

Таким образом, разложение действительно необходимо только в частном случае, где P [i '] == R-i, поэтому мы не знаем, может ли палиндром в P [i] быть длиннее.

Это обрабатывается в фактическом коде, устанавливая P [i] = min (P [i '], R-i), а затем всегда расширяясь. Этот способ сделать это не увеличивает сложность времени, потому что, если расширение не требуется, время, затраченное на выполнение расширения, является постоянным.

Ответ 2

Алгоритм на этом сайте кажется понятным для определенной точки http://www.akalin.cx/longest-palindrome-linear-time

Чтобы понять этот конкретный подход, лучше всего попытаться решить проблему на бумаге и поймать трюки, которые вы можете реализовать, чтобы избежать проверки палиндрома для каждого возможного центра.

Сначала ответьте сами: когда вы найдете палиндром определенной длины, скажем 5 - не можете ли вы, как следующий шаг, просто перейти к концу этого палиндрома (пропуская 4 буквы и 4 средних буквы)?

Если вы попытаетесь создать палиндром длиной 8 и поместите еще один палиндром длиной > 8, центр которого находится в правой части первого палиндрома, вы заметите что-то смешное. Попробуйте: Палиндром длиной 8 - WOWILIKEEKIL - Like + ekiL = 8 Теперь в большинстве случаев вы сможете записать место между двумя 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 #, О, #, W # я, #, L, # я, #, К, #, Е, #]

Фокус в том, что вы уже знаете, что, скорее всего, следующие 7 (8-1) числа после 8 будут такими же, как и на левой стороне, так что следующим шагом будет автоматическая копия 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 #, О, #, W # я, #, L, # я, #, К, #, Е, #, Е, #, К, # я, #, L]

Сделайте пример, что такой прыжок разрушит наше текущее решение и посмотрит, что мы можем заметить.

WOWILIKEEKIL - позволяет попытаться сделать большую палиндром с центром где-то внутри EKIL. Но это невозможно - нам нужно сменить слово EKIL на то, что содержит палиндром. Какие? OOOOOh - это трюк. Единственная возможность иметь больший палиндром с центром в правой части нашего текущего палиндрома состоит в том, что он уже находится в правой (и левой) стороне палиндрома.

Попробуйте построить один на основе WOWILIKEEKIL Нам нужно будет сменить EKIL на EKIK, например, на центр большого палиндрома - не забудьте изменить LIKE на KIKE. Первые буквы нашего сложного палиндрома будут:

WOWIKIKEEKIK

как было сказано ранее, пусть последний будет центром большего паллиндрома, чем KIKEEKIK:

WOWIKIKEEKIKEEKIKIW

сделайте массив до нашего старого pallindrom и узнайте, как добавить дополнительную информацию.

для

[_ W _ O _ W _ я _ K _ я _ K _ E _ E _ K _ я _ K _ E _ E _ K _ я _ K _ я _ W]

это будет [0,1,0,3,0,1,0,1,0,3,0,3,0,1,0,1,8

мы знаем, что следующий я - третий будет самым длинным pallindrome, но пусть забудет об этом немного. позволяет скопировать числа в массиве слева от 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]

В нашем цикле мы находимся между E с номером 8. Что особенного в я (будущий средний самый большой паллиндром), что мы не можем прыгнуть прямо на K (последняя буква самого большого паллиндром)? Особо то, что он превышает текущий размер массива... как? Если вы перемещаете 3 пробела справа от 3 - вы вне массива. Это означает, что это может быть середина самого большого паллиндром, и самое дальнее, что вы можете прыгнуть, это письмо I.

Извините за длину этого ответа - я хотел объяснить алгоритм и может вас заверить - @OmnipotentEntity был прав - я понимаю его еще лучше после объяснения вам:)

Ответ 3

Я нашел одно из лучших объяснений до сих пор по следующей ссылке:

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

Он также имеет визуализацию для одного и того же строкового примера (babcbabcbaccba), используемого в первой ссылке, упомянутой в вопросе.

Помимо этой ссылки, я также нашел код в

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

Я надеюсь, что это будет полезно для других, которые пытаются понять суть этого алгоритма.

Ответ 4

Полная статья: http://www.zrzahid.com/longest-palindromic-substring-in-linear-time-manachers-algorithm/

Прежде всего, давайте внимательно наблюдать за палиндром, чтобы найти интересные свойства. Например, S1 = "abaaba" и S2 = "abcba", оба являются палиндром, но что такое нетривиальная (то есть не длина или символ) разница между ними? S1 - палиндром, сосредоточенный вокруг невидимого пространства между я = 2 и я = 3 (несуществующее пространство!). С другой стороны, S2 центрируется вокруг символа при я = 2 (т.е. C). Чтобы любезно обрабатывать центр палиндрома независимо от нечетной/четной длины, можно преобразовать палиндром, вставив специальный символ $между символами. Тогда S1 = "abba" и S2 = "abcba" будут преобразованы в T1 = "$ a $b $a $a $b $a $" с центром в я = 6 и T2 = "$ a $b $c $b $a $" с центром в я = 5. Теперь мы можем видеть, что центры существуют, а длины согласованы 2 * n + 1, где n = длина исходной строки. Например,

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

Далее заметим, что из симметричного свойства (трансформированного) палиндрома T вокруг центра c T [c-k] = T [c + k] для 0 <= k <= c. То есть позиции c-k и c + k зеркало друг к другу. Иначе говоря, для индекса я справа от центра c индекс зеркала я 'находится слева от c, так что c-i' = i-c = > я '= 2 * c-i и наоборот. То есть

Для каждой позиции я справа от центра c палиндромной подстроки положение зеркала я равно я '= 2 * c-i и наоборот.

Определим массив P [0..2 * n] такой, что P [i] равен длине палиндрома с центром в i. Обратите внимание, что длина фактически измеряется количеством символов в исходной строке (игнорируя специальные символы $). Пусть также min и max являются соответственно самой левой и самой правой границей палиндромной подстроки с центром в точке c. Итак, min = c-P [c] и max = c + P [c]. Например, для палиндрома S = "abaaba", преобразованного палиндрома T, центра зеркала c = 6, массива длины P [0,12], min = cP [c] = 6-6 = 0, max = c + P [c] = 6 + 6 = 12, а два примера зеркальных индексов я и я 'показаны на следующем рисунке.

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

С таким массивом длины P мы можем найти длину самой длинной палиндромной подстроки, посмотрев на макс элемент P. То есть

P [i] - длина палиндромной подстроки с центром в я в преобразованной строке T, т.е. центр в i/2 в исходной строке S; Следовательно, самая длинная палиндромная подстрока будет подстрокой длины P [i _max], начиная с индекса (i _max -P [i _max])/2, так что я _max - это индекс максимального элемента в P.

Приведем аналогичную фигуру в следующей строке для непалиндромного примера 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 |
      ---------------------------------------------------------------------

Вопрос заключается в том, как эффективно вычислить P. Симметричное свойство предлагает следующие случаи, которые мы могли бы потенциально использовать для вычисления P [i], используя ранее вычисленный P [i '] в зеркальном индексе i' слева, и, следовательно, пропускаем множество вычислений. Предположим, что у нас есть исходный палиндром (первый палиндром).

•   

• Третий палиндром, центр которого находится в правой части первого палиндрома, будет иметь ту же длину, что и второй палиндром, закрепленный в зеркальном центре на левой стороне, если второй палиндром находится в пределах первого палиндрома по меньшей мере одним символом.

  Например, на следующем рисунке с первым палиндром, центрированным при c = 8 и ограниченным min = 4 и max = 12, длина третьего палиндром с центром в я = 9 (с зеркальным индексом я '= 2 * ci = 7) равна, P [i] = P [i '] = 1. Это связано с тем, что второй палиндром с центром в i' находится в пределах первого палиндрома. Аналогично, 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 | ? | ? | ? | ? | ? | ? | ? | ? |
        ---------------------------------------------------------------------
  

  Теперь вопрос заключается в том, как проверить этот случай? Заметим, что из-за симметричной длины свойства сегмента [min..i '] равна длине сегмента [i..max]. Также обратите внимание, что 2-й палиндром полностью находится в 1-м палиндром, если левый край 2-го палиндрома находится внутри левой границы, мин 1-го палиндрома. То есть,

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

  Объединяя все факты в случае 1,

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

• Если второй палиндром встречается или выходит за пределы левой границы первого палиндрома, то гарантируется, что третий палиндром имеет, по меньшей мере, длину от своего собственного центра до правого внешнего символа первого палиндрома. Эта длина одинакова от центра второго палиндрома до левого внешнего символа первого палиндрома.

  Например, на следующем рисунке второй палиндром с центром в я = 5 выходит за пределы левой границы первого палиндрома. Итак, в этом случае мы не можем сказать P [i] = P [i ']. Но длина третьего палиндрома с центром в точке я = 11, P [i] составляет, по меньшей мере, длину от ее центра я = 11 до правой границы max = 12 первого палиндром с центром в c. То есть P [i] >= 1. Это означает, что третий палиндром может быть продлен за макс, если и только если следующий немедленный символ прошлых макс совпадает с зеркальным символом, и мы продолжаем эту проверку дальше. Например, в этом случае P [13]!= P [9], и он не может быть расширен. Итак, 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 | ? | ? | ? | ? | ? | ? |
        ---------------------------------------------------------------------
  

  Итак, как проверить этот случай? Это просто неудачная проверка для случая 1. То есть второй палиндром будет проецировать предыдущий левый край первого палиндрома 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]. 
  

  То есть P [i] не меньше (max-i) iff (max-i) P [i] >= (max-i), iff (max-i) Теперь, если третий палиндром выходит за пределы максимума, нам нужно обновить центр и границу нового палиндрома.

  Если палиндром в центре я расширяется за макс, тогда у нас есть новый (расширенный) палиндром, следовательно, новый центр в c = i. Обновите max до самой правой границы нового палиндрома.

  Объединяя все факты в случае 1 и 2, мы можем придумать очень красивые формулы:

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

  То есть, P [i] = min (P [i '], max-i), когда третий палиндром не расширяется до макс. В противном случае мы имеем новый третий палиндром в центре при c = я и новый max = я + P [i].

• Ни первый, ни второй палиндром не предоставляют информацию, чтобы помочь определить палиндромную длину четвертого палиндрома, центр которого находится за правой стороной первого палиндрома.

  То есть мы не можем определить превентивно P [i], если i > max. То есть,

  P [i] = 0, iff max-i &lt 0

  Объединяя все случаи, заключаем формулы:

  P [i] = max > i? min (P [i '], max-i): 0. В случае, если мы можем выходить за пределы max, мы расширяем путем сопоставления символов за пределами max с зеркальным характером относительно нового центра при c = i. Наконец, когда у нас есть несоответствие, мы обновляем новый max = я + P [i].

Ссылка: описание алгоритма на странице wiki

Ответ 5

Я сделал видео по этому алгоритму, используя анимационную графику. Надеюсь, это поможет вам это понять! https://www.youtube.com/watch?v=kbUiR5YWUpQ

Ответ 6

Этот материал очень помогает мне понять это: http://solutionleetcode.blogspot.com/2013/07/leetcode-longest-palindromic-substring.html

Определите T как длину самых длинных палиндромных подстрок, центрированных на каждом из символов.

Главное, когда маленькие палиндромы полностью внедрены в длинный палиндром, T [i] также должен быть симметричным в пределах более длинного палиндрома.

В противном случае нам придется вычислять T [i] с нуля, а не индуцировать из симметричной левой части.

Ответ 7

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

Ответ 8

Быстрый Javascript Решение для поиска самого длинного палиндрома в строке:

const lpal = str => {
  let lpal = ""; // to store longest palindrome encountered
  let pal = ""; // to store new palindromes found
  let left; // to iterate through left side indices of the character considered to be center of palindrome
  let right; // to iterate through left side indices of the character considered to be center of palindrome
  let j; // to iterate through all characters and considering each to be center of palindrome
  for (let i=0; i<str.length; i++) { // run through all characters considering them center of palindrome
    pal = str[i]; // initializing current palindrome
    j = i; // setting j as index at the center of palindorme
    left = j-1; // taking left index of j
    right = j+1; // taking right index of j
    while (left >= 0 && right < str.length) { // while left and right indices exist
      if(str[left] === str[right]) { //
        pal = str[left] + pal + str[right];
      } else {
        break;
      }
      left--;
      right++;
    }
    if(pal.length > lpal.length) {
      lpal = pal;
    }
    pal = str[i];
    j = i;
    left = j-1;
    right = j+1;
    if(str[j] === str[right]) {
      pal = pal + str[right];
      right++;
      while (left >= 0 && right < str.length) {
        if(str[left] === str[right]) {
          pal = str[left] + pal + str[right];
        } else {
          break;
        }
        left--;
        right++;
      }
      if(pal.length > lpal.length) {
        lpal = pal;
      }
    }
  }
  return lpal;
}

Пример ввода

console.log(lpal("gerngehgbrgregbeuhgurhuygbhsbjsrhfesasdfffdsajkjsrngkjbsrjgrsbjvhbvhbvhsbrfhrsbfsuhbvsuhbvhvbksbrkvkjb"));

Выход

asdfffdsa

Ответ 9

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