Поиск длиннейшей подстроки-палиндрома

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

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

Примечания

1. Crochemore & Rytter (1991), Apostolico, Breslauer & Galil (1995).

Литература

• 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, 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, MR 1272521.
• 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 Архивная копия от 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, Дата обращения: 22 ноября 2011. An explanation and Python implementation of Manacher’s linear-time algorithm.
• Jeuring, Johan (2007-2010), Palindromes, Дата обращения: 22 ноября 2011. Haskell implementation of Jeuring’s linear-time algorithm.
• Palindromes (недоступная ссылка). 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.