Самая длинная палиндромная подстрока - Longest palindromic substring - Wikipedia

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

Манахер (1975) изобрел линейное время алгоритм для перечисления всех палиндромов, которые появляются в начале данной строки. Однако, как заметил, например, Апостолико, Бреслауэр и Галил (1995), тот же алгоритм можно также использовать для поиска всех максимальных палиндромных подстрок в любом месте входной строки, снова за линейное время. Таким образом, он обеспечивает линейное решение самой длинной проблемы палиндромной подстроки. Альтернативные решения для линейного времени были предоставлены Jeuring (1994), и по Гасфилд (1997), который описал решение на основе суффиксные деревья. Эффективный параллельные алгоритмы также известны своей проблемой.[1]

Проблема с самой длинной палиндромной подстрокой не следует путать с другой проблемой поиска самой длинной палиндромной подстроки. подпоследовательность.

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

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

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


Псевдокод

    заданная строка S строка S '= S с фиктивным символом (например,' | '), вставленным между каждым символом (включая внешние границы) array P = [0, ..., 0] // Чтобы сохранить длины палиндрома для каждая центральная точка в S '// примечание: length (S') = length (P) = 2 × length (S) + 1 // Отслеживаем следующие индексы в P или S 'R = 0 // Следующий элемент, который будет осмотрел; index into S C = 0 // Самый большой / крайний левый палиндром, правая граница которого равна R-1; index into S i = 1 // Следующий вычисляемый палиндром; индекс в P определять L = i - (R - i) // Персонаж-кандидат для сравнения с R; индекс в S определять i '= C - (i - C) // Палиндром, отражающий i от C; индекс в P пока R <длина (S '): Если i находится внутри палиндрома в точке C (случаи 1 и 2): Set P [i] = P [i '] // примечание: отзыв P инициализируется всеми нулями // Раскрытие палиндрома в точке i (в основном случаи 2 и 3; можно пропустить в случае 1, // хотя мы уже показали, что S '[R] ≠ S' [L], потому что в противном случае палиндром // в i 'расширился бы по крайней мере до левого края палиндрома в C) : пока S '[R] == S' [L]: увеличить P [i] увеличить R Если палиндром в i выходит за пределы палиндрома в C: обновить C = i увеличить i возвращаться макс (P)

Это немного отличается от исходного алгоритма Манакера, прежде всего, сознательно объявляя и оперируя р таким образом, чтобы показать, что время выполнения на самом деле линейно. Вы можете видеть в псевдокоде, что р, C и i все монотонно увеличиваются, каждый шаг проходит через элементы в S 'и P. (конечное условие также было немного изменено, чтобы не вычислять последние элементы п если р уже находится в конце - они обязательно будут иметь длину меньше P [C] и могут быть пропущены).

Использование S 'обеспечивает несколько упрощений кода: он предоставляет строку, выровненную по п разрешает прямое использование указателей в обоих массивах и неявно позволяет внутреннему циклу while увеличивать P [i] и R в два раза (потому что каждый раз он будет сравнивать фиктивный символ с самим собой).

Примечания

  1. ^ Крошмор и Риттер (1991), Апостолико, Бреслауэр и Галил (1995).

Рекомендации

  • Апостолико, Альберто; Бреслауэр, Дэни; Галил, Цви (1995), «Параллельное обнаружение всех палиндромов в цепочке», Теоретическая информатика, 141 (1–2): 163–173, Дои:10.1016 / 0304-3975 (94) 00083-У.
  • Крошмор, Максим; Риттер, Войцех (1991), «Полезность алгоритма Карпа – Миллера – Розенберга в параллельных вычислениях на строках и массивах», Теоретическая информатика, 88 (1): 59–82, Дои:10.1016 / 0304-3975 (91) 90073-Б, МИСТЕР  1130372.
  • Крошмор, Максим; Риттер, Войцех (2003), «8.1 Поиск симметричных слов», Драгоценности стрингологии: текстовые алгоритмы, World Scientific, стр. 111–114, ISBN  978-981-02-4897-0.
  • Гасфилд, Дэн (1997), «9.2 Нахождение всех максимальных палиндромов за линейное время», Алгоритмы на строках, деревьях и последовательностях, Кембридж: Издательство Кембриджского университета, стр. 197–199, Дои:10.1017 / CBO9780511574931, ISBN  0-521-58519-8, МИСТЕР  1460730.
  • Джуринг, Йохан (1994), «Вывод онлайн-алгоритмов с приложением для поиска палиндромов», Алгоритмика, 11 (2): 146–184, Дои:10.1007 / BF01182773, HDL:1874/20926, МИСТЕР  1272521, S2CID  7032332.
  • Манахер, Гленн (1975), «Новый алгоритм линейного времени в режиме онлайн для поиска наименьшего начального палиндрома строки», Журнал ACM, 22 (3): 346–351, Дои:10.1145/321892.321896, S2CID  10615419.

внешняя ссылка

Эта статья включает текст из Самая длинная палиндромная подстрока на PEGWiki под лицензией Creative Commons Attribution (CC-BY-3.0 ) лицензия.