Как найти самый длинный палиндром

Алгоритм поиска самой длинной подстроки-палиндрома

Один из самых прекрасных алгоритмов в информатике, который показывает, как можно получить большое ускорение от “вялого” O(n³) до молниеносного¹ O(n), просто посмотрев на проблему с другой точки зрения.

Задача состоит в том, чтобы найти самую длинную подстроку, которая является палиндромом (читается одинаково слева направо и справа налево, например, “racecar”). Так, самый длинный палиндром в строке “Fractions are never odd or even” это “never odd or even” (регистр букв и пробелы игнорируются). Это также имеет практическое применение в биохимии (ГААТТЦ или ЦТТААГ являются палиндромными последовательностями²). К тому же, эту задачу³ часто дают на собеседовании.

Самый простой и прямой подход (при этом самый медленный) – перебирать с начала все подстроки всех длин и проверять, является ли текущая палиндромом:

Псевдокод такого решения

ЦИКЛ по символам всей строки:
	ЦИКЛ по всем длинам, начиная с текущего символа:
		ЦИКЛ по символам в этой подстроке:

явно указывает, что метод со сложностью O(n³) (где n – это длина начальной строки) является быстровозрастающей функцией.

Если бы вместо перебора с самых начал подстрок, мы начинали перебор с середины, это позволило бы нам использовать результаты, которые мы получили на предыдущих шагах.

Например, если мы знаем, что “eve” – это палиндром, то нам потребуется всего одно сравнение, чтобы выяснить, что “level” тоже палиндром. В первом решении нам бы пришлось проверять все полностью с самого начала.

ЦИКЛ по символам строки до середины:
	ЦИКЛ по всем длинам, начиная с текущего символа:

В таком случае сложность составляет O(n²). Но существуют методы⁴, позволяющие сделать это еще быстрее.

Один из самых изящных – это алгоритм Манакера⁵. Он основан на методе, описанном выше, но его временная сложность сокращена до O(n).

Когда палиндромы в строке находятся далеко, оптимизировать нечего. Сложность и так O(n). Проблема появляется, когда они пересекаются, а худшим случаем является строка, состоящая из одной буквы.

Рассмотрим следующую ситуацию. Алгоритм нашел самый короткий зеленый палиндром, самый длинный голубой палиндром и остановился на букве “i”:

Внимательно посмотрев на картинку, можно заметить, что у нас нет необходимости обрабатывать правую часть голубого палиндрома. По определению, это зеркальное отражение левой части, так что полученную левую часть мы можем отразить на правую и получить ее, так сказать, “за бесплатно”.

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

Опять-таки нет нужды дважды проверять длину отраженного палиндрома: буквы b и x обязаны быть различными, иначе голубой палиндром был бы длиннее.

Наконец, один палиндром может “касаться” другого изнутри. В этом случае нет гарантий, что отраженный палиндром не имеет бОльшую длину, так как мы получаем нижнюю границу его длины:

В идеале мы должны пропускать как нулевые, так и строго ненулевые значения (= все случаи, кроме последнего) в дальнейшей обработке (код 1 ниже). Но в практике (если вообще можно говорить о практике в такой абстрактной задаче) разница между ≥ и = довольно мала (всего одно дополнительное сравнение), поэтому имеет смысл рассматривать все ненулевые значения с помощью ≥ для краткости и читаемости кода (код 2 ниже).

Одна из возможных реализаций алгоритма на питоне:

#код 1
def odd(s):
    n = len(s)
    h = [0] * n
    C = R = 0      # центр и радиус или крайний правый палиндром
    besti, bestj = 0, 0     # центр и радиус самого длинного палиндрома
    for i in range(n):
        if i < C + R:         # если есть пересечение
            j = h[C-(i-C)]       # отражение
            if j < C + R - i:    # случай A
                h[i] = j
                continue
            elif j > C + R - i:  # случай B 
                h[i] = C + R - i
                continue
            else:                # case C 
                pass
        else:                 # если нет пересечения
            j = 0
        while i-j > 0 and i+j<n-1 and s[i-j-1] == s[i+j+1]:
            j += 1
        h[i] = j
        if j > bestj:
            besti, bestj = i, j
        if i + j > C + R:
            C, R = i, j
    return s[besti-bestj : besti+bestj+1]

Сперва алгоритм пытается найти соответствующее отражение, как описано выше. Затем, если необходимо, последовательно ищет: как в алгоритме со сложностью O(n²), но принимая отраженное значения за начальную точку. В конце если новый палиндром перекрывает больше текста справа, чем предыдущий, то он становится новым крайним правым палиндромом.

Эта функция ищет палиндромы только нечетного размера. Общий подход для работы с палиндромами четного размера таков:

• вставлять произвольный символ между символами в оригинальной строке, к примеру ‘noon’ -> ‘|n|o|o|n|’,

• находить палиндром нечетного размера,

• удалять произвольные символы из результата.

Символ “|” необязательно должен отсутствовать в строке. Можно использовать любой символ.

def odd_or_even(s):
    return odd('|'+'|'.join(s)+'|').replace('|', '')

>>> odd_or_even('afternoon')
'noon'

Немного запутанная версия (труднее для понимания, немного медленнее, но короче) выглядит так:

#код 2
import re

def odd(s):
    n = len(s)
    h = [0] * n
    C = R = 0      # центр и радиус или крайний правый палиндром
    besti, bestj = 0, 0     # центр и радиус самого длинного палиндрома
    for i in range(n):
        j = 0 if i > C+R else min(h[C-(i-C)], C+R-i)
        while i-j > 0 and i+j<n-1 and s[i-j-1] == s[i+j+1]:
            j += 1
        h[i] = j
        if j > bestj:
            besti, bestj = i, j
        if i + j > C + R:
            C, R = i, j
    return s[besti-bestj : besti+bestj+1]

def manacher(s):
    clean = re.sub('W', '', s.lower())
    return odd('|'+'|'.join(clean)+'|')[1::2]

>>> manacher('He said: "Madam, I'm Adam!"')
'madamimadam'

Как видно, в коде есть два вложенных цикла. Тем не менее, интуитивно понятно, почему сложность O(n). На диаграмме показан массив h.

Внешний цикл соответствует горизонтальному перемещению, внутренний – вертикальному. Каждый шаг – это одно сравнение. Сплошные линии – расчет шагов, пунктирные – пропуск шагов.

Очевидно из диаграммы, что, когда палиндромы не пересекаются, число шагов “вверх” равно количеству горизонтальных “пропускающих” шагов. Для пересекающихся палиндромов чуть более заморочено, но если посчитать число шагов “вверх” и число горизонтальных “пропускающих шагов, то эти числа вновь совпадут. Так что общее число шагов ограничено 2n сравнениями. Не просто n , потому что, в отличие от вертикальных шагов, чтобы понять, пропускать ли горизонтальный шаг или нет, необходимо проделать некую работу (хотя можно изменить реализацию, чтобы пропускать их за постоянное время). Итого временная сложность – O(n).

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

Ссылки:

1. Сайт Big-O Cheat Sheet.

2. Статья на Википедии про палиндромные последовательности.

3. Задача на Leetcode про самый длинный палиндром в строке.

4. Статья на Википедии про самый длинный палиндром в строке.

5. Гленн Манакер (1975), “Новый линейный алгоритм для поиска самого длинного палиндрома строки”, журнал ACM.

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от версии, проверенной 16 июля 2020 года; проверки требуют 2 правки.

В разделе компьютерные науки, задача о самой длинной палиндромиальной подстроке — это задача отыскания самой длинной подстроки данной строки являющейся палиндромом. Например, самая длинная палиндромиальная подстрока «банана» это «анана». Самая длинная палиндромиальная подстрока не обязательно единственна; например в строке «абракадабра» нет палиндромиальной подстроки длиннее трёх символов, но есть состоящие в точности из трёх символов, а именно, «ака» и «ада». В некоторых приложениях требуется найти все максимальные палиндромиальные подстроки (а именно, все подстроки, которые сами по себе являются палиндромами и не могут быть дополнены до более длинных палиндромиальных подстрок) вместо того чтобы вернуть только одну подстроку или вернуть максимальную длину палиндромиальной подстроки.

Manacher (1975) изобрёл линейный по времени алгоритм перечисления всех палиндромов находящихся в начале данной строки. Однако, как было показано Apostolico, Breslauer & Galil (1995), этот же алгоритм может быть использован для нахождения всех самых длинных палиндромиальных подстрок в любом месте данной строки, опять-таки за линейное время. Поэтому он обеспечивает решение задачи нахождения максимальной палиндромиальной подстроки за линейное время. Альтернативные решения, работающие за линейное время, были предложены Jeuring (1994), и Gusfield (1997), который описал решение основанное на использовании суффиксных деревьев. Также известны эффективные параллельные алгоритмы решения этой задачи.^[1]

Задачу нахождения самой длинной палиндромиальной подстроки не следует путать с задачей нахождения самой длинной палиндромиальной подпоследовательности.

Алгоритм Манакера[править | править код]

Чтобы за линейное время найти в строке самый длинный палиндром, алгоритм может воспользоваться следующими свойствами палиндромов и подпалиндромов:

1. Левая часть палиндрома является зеркальным отражением его правой части
2. (Случай 1) Третий палиндром, чей центр лежит в правой части первого палиндрома, будет иметь в точности ту же длину, что и второй палиндром, центр которого зеркально отражен в левую часть, если второй палиндром лежит внутри первого, отступая от границы по крайней мере на один символ.
3. (Случай 2) Если второй палиндром имеет общую границу с первым палиндромом, или простирается за его пределы, то длина третьего палиндрома гарантировано не меньше расстояния от его центра до правой границы первого палиндрома. Эта длина совпадает с расстоянием от центра второго палиндрома до самого левого символа первого палиндрома.
4. Чтобы найти длину третьего палиндрома в случае 2, необходимо сравнивать символы, идущие за самым правым символом первого палиндрома с их зеркальным отражением относительно центра третьего палиндрома пока либо не исчерпается строка, либо не будет обнаружено неравенство символов.
5. (Случай 3) Ни первый, ни второй палиндромы не предоставляют информации, позволяющей определить длину четвёртого палиндрома, чей центр лежит за границей первого палиндрома.
6. Поэтому для определения слева направо палиндромиальных длин подстрок в строке желательно иметь опорный палиндром (исполняющий роль первого палиндрома), чьи символы занимают самые правые положения в строке (и, следовательно, третий палиндром в случае 2 и четвёртый палиндром в случае 3 могут заменять первый палиндром, чтобы стать новым опорным палиндромом).
7. Что касается оценки времени определения палиндромиальный длины для каждого символа строки: в Случае 1 сравнения символов не производится, в Случаях 2 и 3 кандидатами для сравнения являются только символы строки, лежащей за самым правым символом опорного палиндрома (и следовательно Случай 3 всегда приводит к смене опорного палиндрома, когда Случай 2 меняет опорный палиндром только если оказывается что длина третьего палиндрома в действительности больше чем его обещанная минимальная длина).
8. Для палиндромов чётной степени центр лежит между двумя центральными символами палиндрома.

Реализация[править | править код]

Пусть:

• s — строка из N символов
• s2 — производная от s строка, состоящая из N * 2 + 1 элементов, при этом каждый элемент соответствует одному из: N символам в s, N-1 промежутку между символами и границами, и промежуткам, идущим перед первым и за последним символами строки s соответственно
• Границы в s2 ничем не отличаются друг от друга в плане нахождения длины палиндрома
• Пусть p будет массивом радиусов палиндрома, то есть расстоянием от центра до любого из самых дальних символов палиндрома (то есть палиндром длиной 3 имеет палиндромиальный радиус 1)
• Пусть c будет положением центра палиндрома содержащего символ, ближайший к правому концу s2 (длина этого палиндрома p[c]*2+1)
• Пусть r будет положением самой правой границы этого палиндрома (то есть, r = c + p[c])
• Пусть i — положение элемента (то есть промежутка или символа) в s2, чей палиндромиальный радиус определяется, причём i всегда расположено правее c
• Пусть i_mir будет зеркальным отражением i относительно c (то есть, {i, i_mir} = {6, 4}, {7, 3}, {8, 2},… когда c = 5 (значит, i_mir = c * 2 — i))

Результат:
Максимально длинный палиндром, либо первый символ строки

#include <string>
#include <vector>
using namespace std;

string longestPalindrome(const string &s){
    vector<char> s2(s.size() * 2 + 1, '#');
    //создаем псевдостроку с границами в виде символа '#'
    for(int i = 0; i != s.size(); ++i){
        s2[i*2 + 1] = s[i];
    }

    int p[s2.size()];
    int r, c, index, i_mir;
    int maxLen = 1;
    i_mir = index = r = c = 0;

    for(int i = 1; i != s2.size() - 1; ++i){
        i_mir = 2*c-i;

        //Если мы попадаем в пределы радиуса прошлого результата,
        //то начальное значение текущего радиуса можно взять из зеркального результата
        p[i] = r > i ? min(p[i_mir], r-i) : 0;

        while(i > p[i] && (i + p[i] + 1) < s2.size() && s2[i - p[i] - 1] == s2[i + p[i] + 1])
            ++p[i];

        if(p[i] + i > r){
            c = i;
            r = i + p[i];
        }

        if(maxLen < p[i]){
            maxLen = p[i];
            index = i;
        }
    }

    //Отображаем найденные позиции на оригинальную строку
    return s.substr((index-maxLen)/2, maxLen);
}

Примечания[править | править код]

Литература[править | править код]

• Apostolico, Alberto; Breslauer, Dany & Galil, Zvi (1995), Parallel detection of all palindromes in a string, Theoretical Computer Science Т. 141 (1–2): 163–173, DOI 10.1016/0304-3975(94)00083-U.
• Crochemore, Maxime & Rytter, Wojciech (1991), Usefulness of the Karp–Miller–Rosenberg algorithm in parallel computations on strings and arrays, Theoretical Computer Science Т. 88 (1): 59–82, DOI 10.1016/0304-3975(91)90073-B.
• Crochemore, Maxime & Rytter, Wojciech (2003), 8.1 Searching for symmetric words, Jewels of Stringology: Text Algorithms, World Scientific, с. 111–114, ISBN 978-981-02-4897-0.
• Gusfield, Dan (1997), 9.2 Finding all maximal palindromes in linear time, Algorithms on Strings, Trees, and Sequences, Cambridge: Cambridge University Press, с. 197–199, ISBN 0-521-58519-8, DOI 10.1017/CBO9780511574931.
• Jeuring, Johan (1994), The derivation of on-line algorithms, with an application to finding palindromes, Algorithmica Т. 11 (2): 146–184, DOI 10.1007/BF01182773.
• Manacher, Glenn (1975), A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string, Journal of the ACM Т. 22 (3): 346–351, DOI 10.1145/321892.321896.

Ссылки[править | править код]

• Longest Palindromic Substring Part II., 2011-11-20, <http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html> Архивная копия от 2 февраля 2014 на Wayback Machine. A description of Manacher’s algorithm for finding the longest palindromic substring in linear time.
• Akalin, Fred (2007), Finding the longest palindromic substring in linear time, <http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/>. Проверено 22 ноября 2011.. An explanation and Python implementation of Manacher’s linear-time algorithm.
• Jeuring, Johan (2007–2010), Palindromes, <http://www.staff.science.uu.nl/~jeuri101/homepage/palindromes/index.html>. Проверено 22 ноября 2011.. Haskell implementation of Jeuring’s linear-time algorithm.
• Palindromes, <https://github.com/vvikas/palindromes/blob/master/src/LongestPalindromicSubString.java> (недоступная ссылка). Java implementation of Manacher’s linear-time algorithm.

This article incorporates text from Longest palindromic substring on PEGWiki under a Creative Commons Attribution (CC-BY-3.0) license.

From Wikipedia, the free encyclopedia

In computer science, the longest palindromic substring or longest symmetric factor problem is the problem of finding a maximum-length contiguous substring of a given string that is also a palindrome. For example, the longest palindromic substring of “bananas” is “anana”. The longest palindromic substring is not guaranteed to be unique; for example, in the string “abracadabra”, there is no palindromic substring with length greater than three, but there are two palindromic substrings with length three, namely, “aca” and “ada”. In some applications it may be necessary to return all maximal palindromic substrings (that is, all substrings that are themselves palindromes and cannot be extended to larger palindromic substrings) rather than returning only one substring or returning the maximum length of a palindromic substring.

Manacher (1975) invented an -time algorithm for listing all the palindromes that appear at the start of a given string of length . However, as observed e.g., by Apostolico, Breslauer & Galil (1995), the same algorithm can also be used to find all maximal palindromic substrings anywhere within the input string, again in time. Therefore, it provides an -time solution to the longest palindromic substring problem. Alternative -time solutions were provided by Jeuring (1994), and by Gusfield (1997), who described a solution based on suffix trees. A faster algorithm can be achieved in the word RAM model of computation if the size of the input alphabet is in . In particular, this algorithm runs in time using space.^[1] Efficient parallel algorithms are also known for the problem.^[2]

The longest palindromic substring problem should not be confused with the different problem of finding the longest palindromic subsequence.

Slow algorithm[edit]

This algorithm is slower than Manacher’s algorithm, but is a good stepping stone for understanding Manacher’s algorithm. It looks at each character as the center of a palindrome and loops to determine the largest palindrome with that center.

The loop at the center of the function only works for palindromes where the length is an odd number. The function works for even-length palindromes by modifying the input string. The character ‘|’ is inserted between every character in the inputs string, and at both ends. So the input “book” becomes “|b|o|o|k|”. The even-length palindrome “oo” in “book” becomes the odd-length palindrome “|o|o|”.

    Longest_Palindrome_SLOW(string S, string S') {
        // S' == S with a bogus character (eg. '|') inserted 
        // between each character (including outer boundaries)

        // The radius of the longest palindrome centered on each place in S'
        // note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1

        array PalindromeRadii = [0,...,0]
        
        Center = 0

        while Center < length(S') {
            // Determine the longest palindrome starting 
            // at Center-Radius and going to Center+Radius
            Radius = 0

            while Center-(Radius + 1) >= 0 and 
                  Center+(Radius + 1) < length(S') and 
                  S'[Center-(Radius + 1)] = S'[Center+(Radius + 1)] {
                Radius = Radius + 1
            }
            
            // Save the radius of the longest palindrome in the array

            PalindromeRadii[Center] = Radius
            
            Center = Center + 1
        }   
                 
        // One can show that longest_palindrome_in_S is max(PalindromeRadii).
        // if S'[i] == '|', PalindromeRadii[i] is even, otherwise you could increase PalindromeRadii[i] by 1,
        // which is equivalent to inserting an extra '|' in each border.
        // Remember that a palindrome centered in an '|' in S' corresponds to an even palindrome in S.
        // if S'[i] != '|', PalindromeRaii[i] is odd (same argument), and corresponds to an odd palindrome.
        // In this case, the length of the palindrome
        // centered at that character is also x=PalindromeRaii[i], as we have (x-1)/2 characters on each side,
        // plus the extra middle one ((x-1)/2*2+1=x)
        longest_palindrome_in_S = max(PalindromeRadii)

        return longest_palindrome_in_S 
    }

The runtime of this algorithm is . The outer loop runs times and the inner loop can run up to times.

Manacher’s algorithm[edit]

Below is the pseudocode for Manacher’s algorithm. The algorithm is faster than the previous algorithm because it exploits when a palindrome happens inside another palindrome.

For example, consider the input string “abacaba”. By the time it gets to the “c”, Manacher’s algorithm will have identified the length of every palindrome centered on the letters before the “c”. At the “c”, it runs a loop to identify the largest palindrome centered on the “c”: “abacaba”. With that knowledge, everything after the “c” looks like the reflection of everything before the “c”. The “a” after the “c” has the same longest palindrome as the “a” before the “c”. Similarly, the “b” after the “c” has a longest palindrome that is at least the length of the longest palindrome centered on the “b” before the “c”. There are some special cases to consider, but that trick speeds up the computation dramatically.^{[citation needed]}

    Longest_Palindrome(string S, string S') {
        // S' == S with a bogus character (eg. '|') inserted 
        // between each character (including outer boundaries)

        // The radius of the longest palindrome centered on each place in S'
        // note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1

        array PalindromeRadii = [0,...,0]
        
        Center = 0
        Radius = 0
        
        while Center < length(S') {
	    // At the start of the loop, Radius is already set to a lower-bound
	    // for the longest radius. In the first iteration, Radius is 0, but
	    // it can be higher on later iterations.
            
	    // Determine the longest palindrome starting at Center-Radius and
	    // going to Center+Radius

            while Center-(Radius+1) >= 0 and 
	          Center+(Radius+1) < length(S') and 
		  S'[Center-(Radius+1)] = S'[Center+(Radius+1)] {
                Radius = Radius+1
            }             
         
            // Save the radius of the longest palindrome in the array
            PalindromeRadii[Center] = Radius
            
            // Below, Center is incremented.
            // If any precomputed values can be reused, they are.
            // Also, Radius may be set to a value greater than 0
            
            OldCenter = Center
            OldRadius = Radius
            Center = Center+1

	    // Radius' default value will be 0, if we reach the end of the
	    // following loop. 
            Radius = 0 

            while Center <= OldCenter + OldRadius {

		// Because Center lies inside the old palindrome and every
		// character inside a palindrome has a "mirrored" character
		// reflected across its center, we can use the data that was
		// precomputed for the Center's mirrored point. 

                MirroredCenter = OldCenter - (Center - OldCenter)
                MaxMirroredRadius = OldCenter + OldRadius - Center

                if PalindromeRadii[MirroredCenter] < MaxMirroredRadius {

		    // The palindrome centered at MirroredCenter is entirely
		    // contained in the palindrome centered at OldCenter So,
		    // MirroredCenter and Center have the same sized palindrome

                    PalindromeRadii[Center] = PalindromeRadii[MirroredCenter]
                    Center = Center+1
                } else if PalindromeRadii[MirroredCenter] > MaxMirroredRadius {
                
		    // The palindrome at MirroredCenter extends beyond the
		    // palindrome at OldCenter The palindrome at Center must
		    // end at the edge of the OldCenter palindrome Otherwise,
		    // the palindrome at OldCenter would be bigger

                    PalindromeRadii[Center] = MaxMirroredRadius
                    Center = Center+1
                } else { // PalindromeRadii[MirroredCenter] = MaxMirroredRadius

		    // Since the palindrome at MirroredCenter ends exactly at
		    // the edge of the palindrome centered at OldCenter, the
		    // palindrome at Center might be bigger Set Radius to the
		    // minimum size of the palindrome at Center so it doesn't
		    // recheck unnecessarily 

                    Radius = MaxMirroredRadius
                    break
                }   
            }      
        }

	// A palindrome's size is equal to its radius * 2. However, since our
	// variable Radius considers our bogus characters to the side of the
	// center, the size of its corresponding palindrome is actually 2 *
	// (Radius / 2), which means a palindrome's size is equal to its
	// corresponding Radius value in PalindromeRadii

        longest_palindrome_in_S = max(PalindromeRadii)
        return longest_palindrome_in_S
    }

Special Cases[edit]

Manacher’s algorithm is faster because it reuses precomputed data when a palindrome exists inside another palindrome. There are 3 cases of this. They are represented by the “if / else if / else” statement in the pseudocode.

The first case is when the palindrome at MirroredCenter lies completely inside the “Old” palindrome. In this situation, the palindrome at Center will have the same length as the one at MirroredCenter. For example, if the “Old” palindrome is “abcbpbcba”, we can see that the palindrome centered on “c” after the “p” must have the same length as the palindrome centered on the “c” before the “p”.

The second case is when the palindrome at MirroredCenter extends outside the “Old” palindrome. That is, it extends “to the left” (or, contains characters with a lower index than any inside the “Old” palindrome). Because the “Old” palindrome is the largest possible palindrome centered on OldCenter, we know the characters before and after it are different. Thus, the palindrome at Center will run exactly up to the border of the “Old” palindrome, because the next character will be different than the one inside the palindrome at MirroredCenter. For example, if the string was “ababc”, the “Old” palindrome could be “bab” with the Center being the second “b” and the MirroredCenter being the first “b”. Since the palindrome at the MirroredCenter is “aba” and extends beyond the boundaries of the “Old” palindrome, we know the longest palindrome at the second “b” can only extend up to the border of the “Old” palindrome. We know this because if the character after the “Old” palindrome had been an “a” instead of a “c”, the “Old” palindrome would have been longer.

The third and last case is when the palindrome at MirroredCenter extends exactly up to the border of the “Old” palindrome. In this case, we don’t know if the character after the “Old” palindrome might make the palindrome at Center longer than the one at MirroredCenter. But we do know that the palindrome at Center is at least as long as the one at MirroredCenter. In this case, Radius is initialized to the radius of the palindrome at MirroredCenter and the search starts from there. An example string would be “abcbpbcbp” where the “Old” palindrome is “bcbpbcb” and the Center is on the second “c”. The MirroredCenter is the first “c” and it has a longest palindrome of “bcb”. The longest palindrome at the Center on the second “c” has to be at least that long and, in this case, is longer.

Runtime[edit]

The algorithm runs in linear time. This can be seen by noting that Center strictly increases after each outer loop and the sum Center + Radius is non-decreasing. Moreover, the number of operations in the first inner loop is linear in the increase of the sum Center + Radius while the number of operations in the second inner loop is linear in the increase of Center. Since Center ≤ 2n+1 and Radius ≤ n, the total number of operations in the first and second inner loops is and the total number of operations in the outer loop, other than those in the inner loops, is also . The overall running time is therefore .

Notes[edit]

References[edit]

• Apostolico, Alberto; Breslauer, Dany; Galil, Zvi (1995), “Parallel detection of all palindromes in a string”, Theoretical Computer Science, 141 (1–2): 163–173, doi:10.1016/0304-3975(94)00083-U.
• Charalampopoulos, Panagiotis; Pissis, Solon P.; Radoszewski, Jakub (2022), “Longest Palindromic Substring in Sublinear Time”, 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, June 27-29, 2022, Prague, Czech Republic, 223: 20:1–20:9, doi:10.4230/LIPIcs.CPM.2022.20.
• Crochemore, Maxime; Rytter, Wojciech (1991), “Usefulness of the Karp–Miller–Rosenberg algorithm in parallel computations on strings and arrays”, Theoretical Computer Science, 88 (1): 59–82, doi:10.1016/0304-3975(91)90073-B, MR 1130372.
• Crochemore, Maxime; Rytter, Wojciech (2003), “8.1 Searching for symmetric words”, Jewels of Stringology: Text Algorithms, World Scientific, pp. 111–114, ISBN 978-981-02-4897-0.
• Gusfield, Dan (1997), “9.2 Finding all maximal palindromes in linear time”, Algorithms on Strings, Trees, and Sequences, Cambridge: Cambridge University Press, pp. 197–199, doi:10.1017/CBO9780511574931, ISBN 0-521-58519-8, MR 1460730.
• Jeuring, Johan (1994), “The derivation of on-line algorithms, with an application to finding palindromes”, Algorithmica, 11 (2): 146–184, doi:10.1007/BF01182773, hdl:1874/20926, MR 1272521, S2CID 7032332.
• Manacher, Glenn (1975), “A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string”, Journal of the ACM, 22 (3): 346–351, doi:10.1145/321892.321896, S2CID 10615419.

External links[edit]

• Longest Palindromic Substring Part II., 2011-11-20, archived from the original on 2018-12-08. A description of Manacher’s algorithm for finding the longest palindromic substring in linear time.
• Akalin, Fred (2007-11-28), Finding the longest palindromic substring in linear time, retrieved 2016-10-01. An explanation and Python implementation of Manacher’s linear-time algorithm.
• Jeuring, Johan (2007–2010), Palindromes, retrieved 2011-11-22. Haskell implementation of Jeuring’s linear-time algorithm.
• Palindromes (deadlink). Java implementation of Manacher’s linear-time algorithm.

This article incorporates text from Longest palindromic substring on PEGWiki under a Creative Commons Attribution (CC-BY-3.0) license.

“Перевел” код с приведенной вами страницы на python3:

def palSubSeq(L, string, left, right):
    if L[left][right] == -1:
        if string[left] == string[right]:
            L[left][right] = palSubSeq(L, string, left+1, right-1) + 2
        else:
            L[left][right] = max(palSubSeq(L, string, left+1, right) , palSubSeq(L, string, left, right-1))
    return L[left][right]

def palChars(L, palindrome, left, right, palLeft, palRight):
    while left <= right:
        if left==right and L[left][right]==1:
            palindrome[palLeft] = string[left]
            palLeft += 1
            left += 1
        else:
            if string[left] == string[right]:
                palindrome[palLeft] = string[left]
                palLeft += 1
                left += 1

                palindrome[palRight] = string[right]
                palRight -= 1
                right -= 1
            else:
                if L[left+1][right] >= L[left][right-1]:
                    left += 1
                else:
                    right -= 1

def search_pal(string):
    N = len(string)
    palindrome = ['_' for _ in range(N)]
    L = [[-1] * N for _ in range(N)]

    for i in range(N):
        for j in range(N):
            if i==j:
                L[i][j] = 1
            elif i>j:
                L[i][j] = 0
    palSubSeq(L, string, 0, N-1)
    palChars(L, palindrome, 0, N-1, 0, L[0][N-1])
    return ''.join(filter('_'.__ne__, palindrome)) 

string = 'oro'
if string == string[::-1]:
    palindrome = string[::-1]
else:
    palindrome = search_pal(string)
print(palindrome)