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

Материал из Поле цифровой дидактики
Версия от 14:11, 23 июля 2022; ru_wikipedia>Lumaca (Добавлена Категория:Палиндром с помощью HotCat)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

Шаблон:Harvtxt изобрёл линейный по времени алгоритм перечисления всех палиндромов находящихся в начале данной строки. Однако, как было показано Шаблон:Harvtxt, этот же алгоритм может быть использован для нахождения всех самых длинных палиндромиальных подстрок в любом месте данной строки, опять-таки за линейное время. Поэтому он обеспечивает решение задачи нахождения максимальной палиндромиальной подстроки за линейное время. Альтернативные решения, работающие за линейное время, были предложены Шаблон:Harvtxt, и Шаблон:Harvtxt, который описал решение основанное на использовании суффиксных деревьев. Также известны эффективные параллельные алгоритмы решения этой задачи.<ref>Шаблон:Harvtxt, Шаблон:Harvtxt.</ref>

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

Алгоритм Манакера

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

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

Примечания

Шаблон:Примечания

Литература

Ссылки

This article incorporates text from Longest palindromic substring on PEGWiki under a Creative Commons Attribution (CC-BY-3.0) license.
Источник — http://digida.mgpu.ru/index.php?title=Поиск_длиннейшей_подстроки-палиндрома&oldid=4660