Самая длинная палиндромная подстрока

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

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

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

• 1 Медленный алгоритм
• 2 Алгоритм Манахера
  • 2.1 Особые случаи
  • 2.2 Время выполнения
• 3 Примечания
• 4 ссылки
• 5 Внешние ссылки

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

Цикл в центре функции работает только для палиндромов, длина которых является нечетным числом. Функция работает для палиндромов четной длины путем изменения входной строки. Персонаж '|' вставляется между каждым символом входной строки и с обоих концов. Таким образом, входная «книга» становится «| b | o | o | k |». Палиндром четной длины «oo» в «book» становится палиндромом нечетной длины «| o | o |».

 Longest_Palindrome_SLOW(string S) { string S' = S with a bogus character (eg. '|') inserted between each character (including outer boundaries) array PalindromeRadii = [0,...,0] // The radius of the longest palindrome centered on each place in S' // note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1 Center = 0 while Center lt; length(S') { // Determine the longest palindrome starting at Center-Radius and going to Center+Radius Radius = 0 while Center-(Radius+1) gt;= 0 and Center+(Radius+1) lt; 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 } longest_palindrome_in_S' = 2*max(PalindromeRadii)+1 longest_palindrome_in_S = (longest_palindrome_in_S'-1)/2 return longest_palindrome_in_S }

Время выполнения этого алгоритма. Внешний цикл выполняется раз, а внутренний цикл может выполняться до раз. ${\ Displaystyle О (п ^ {2})}$${\ displaystyle n}$${\ displaystyle n / 2}$

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

Например, рассмотрим входную строку «абакаба». К тому времени, когда он дойдет до «c», алгоритм Манахера определит длину каждого палиндрома с центром на буквах перед «c». В точке «с» он запускает цикл, чтобы определить самый большой палиндром с центром в «с»: «абакаба». С учетом этого, все, что находится после буквы «с», выглядит как отражение всего, что находится до буквы «с». Буква «а» после «с» имеет тот же самый длинный палиндром, что и «а» перед «с». Точно так же буква «b» после «c» имеет самый длинный палиндром, который, по крайней мере, равен длине самого длинного палиндрома с центром на «b» перед «c». Есть несколько особых случаев, которые следует учитывать, но этот трюк значительно ускоряет вычисления.

 Longest_Palindrome(string S) { string S' = S with a bogus character (eg. '|') inserted between each character (including outer boundaries) array PalindromeRadii = [0,...,0] // The radius of the longest palindrome centered on each place in S' // note: length(S') = length(PalindromeRadii) = 2 × length(S) + 1 Center = 0 Radius = 0 while Center lt; 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. // Determine the longest palindrome starting at Center-Radius and going to Center+Radius while Center-(Radius+1) gt;= 0 and Center+(Radius+1) lt; 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 lt;= 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] lt; MaxMirroredRadius { PalindromeRadii[Center] = PalindromeRadii[MirroredCenter] Center = Center+1 } else if PalindromeRadii[MirroredCenter] gt; MaxMirroredRadius { PalindromeRadii[Center] = MaxMirroredRadius Center = Center+1 } else { // PalindromeRadii[MirroredCenter] = MaxMirroredRadius Radius = MaxMirroredRadius break // exit while loop early } } } longest_palindrome_in_S' = 2*max(PalindromeRadii)+1 longest_palindrome_in_S = (longest_palindrome_in_S'-1)/2 return longest_palindrome_in_S }

Особые случаи

Алгоритм Манакера быстрее, потому что он повторно использует предварительно вычисленные данные, когда палиндром существует внутри другого палиндрома. Таких случаев 3. Они представлены оператором if / else if / else в псевдокоде.

Первый случай, когда палиндром at MirroredCenterполностью лежит внутри «Старого» палиндрома. В этой ситуации палиндром at Centerwill будет иметь ту же длину, что и палиндром at MirroredCenter. Например, если «Старый» палиндром - «abcbpbcba», мы можем видеть, что палиндром с центром на «c» после «p» должен иметь ту же длину, что и палиндром с центром на «c» перед «p».

Второй случай - это когда палиндром MirroredCenterвыходит за пределы «Старого» палиндрома. То есть он простирается «влево» (или содержит символы с более низким индексом, чем любой внутри «Старого» палиндрома). Поскольку «Старый» палиндром - это самый большой из возможных палиндромов с центром OldCenter, мы знаем, что символы до и после него различны. Таким образом, палиндром at Centerwill будет работать точно до границы «старого» палиндрома, потому что следующий символ будет отличаться от символа внутри палиндрома at MirroredCenter. Например, если строка была «ababc», «Старый» палиндром мог быть «bab» со Centerвторым «b» и MirroredCenterпервым «b». Поскольку палиндром в точке MirroredCenteris «aba» и выходит за границы «старого» палиндрома, мы знаем, что самый длинный палиндром на втором месте «b» может доходить только до границы «старого» палиндрома. Мы знаем это, потому что если бы символ после «Старого» палиндрома был «а» вместо «с», «Старый» палиндром был бы длиннее.

Третий и последний случай, когда палиндром в точке MirroredCenterпростирается точно до границы «Старого» палиндрома. В этом случае мы не знаем, может ли персонаж после «Старого» палиндрома сделать палиндром Centerдлиннее, чем тот, который находится в MirroredCenter. Но мы знаем, что палиндром на Centerэто, по крайней мере до тех пор, как один в MirroredCenter. В этом случае Radiusинициализируется радиус палиндрома в, MirroredCenterи поиск начинается оттуда. Примерной строкой может быть «abcbpbcbp», где «Старый» палиндром - «bcbpbcb», а Centerвторой - «c». Это MirroredCenterпервая буква «с», и у нее самый длинный палиндром «bcb». Самый длинный палиндром у Centerвторой буквы «c» должен быть не меньше этой длины, а в данном случае - длиннее.

Время выполнения

Алгоритм работает за линейное время. Это можно увидеть, установив границы того, сколько итераций выполняется в каждом цикле. Внешний контур и второй внутренний цикл приращения Centerпо для каждой итерации. Поскольку длина строки ограничена, мы знаем время выполнения этих циклов. Приращения цикла Первые внутренние по для каждой итерации, и второй внутренний цикл, когда он останавливается, декрементирует самое большее для каждой итерации. Поскольку второй внутренний цикл может выполняться в большинстве случаев, а значение для не может превышать значение, первый внутренний цикл может выполняться в большинстве случаев. Общее время выполнения${\ displaystyle 1}$Center${\ displaystyle n}$Radius${\ displaystyle 1}$Radius${\ displaystyle 1}$${\ displaystyle n}$Radius${\ displaystyle n / 2,}$${\ Displaystyle п + п / 2}$${\ Displaystyle О \ влево (п + п + п / 2 \ вправо) = О (п).}$

• Апостолико, Альберто; Бреслауэр, Дэни; Galil, Цви (1995), "Параллельное обнаружение всех палиндромов в строке", Теоретическая информатика, 141 (1-2): 163-173, DOI : 10,1016 / 0304-3975 (94) 00083-U.
• Крошмор, Максим; Rytter, Войцех (1991), "Полезность алгоритма Карп-Миллера-Розенберг в параллельных вычислений на строках и массивах", Теоретическая информатика, 88 (1): 59-82, DOI : 10,1016 / 0304-3975 (91) 90073 -B, Руководство по ремонту   1130372.
• Крошмор, Максим; Риттер, Войцех (2003), «8.1 Поиск симметричных слов», Jewels Stringology: Text Algorithms, World Scientific, стр. 111–114, ISBN   978-981-02-4897-0.
• Гасфилд, Дэн (1997), «9.2 Нахождение всех максимальных палиндромов за линейное время», Алгоритмы на строках, деревьях и последовательностях, Кембридж: Cambridge University Press, стр. 197–199, DOI : 10.1017 / CBO9780511574931, ISBN   0-521-58519-8, Руководство по ремонту   1460730.
• Jeuring, Йохан (1994), "Вывод он-лайн алгоритмов, с приложением к поиску палиндромы", Algorithmica, 11 (2): 146-184, DOI : 10.1007 / BF01182773, ЛВП : 1874/20926, МР   1272521, S2CID   7032332.
• Manacher, Гленн (1975), «Новый линейный времени„он-лайн“алгоритм для нахождения наименьшего начального палиндром строки», Журнал ACM, 22 (3): 346-351, DOI : 10,1145 / 321892,321896, S2CID   10615419.

• Самая длинная палиндромная подстрока. Часть II., 2011-11-20, архивировано из оригинала 2018-12-08. Описание алгоритма Манахера для поиска самой длинной палиндромной подстроки за линейное время.
• Акалин, Фред (2007-11-28), Поиск самой длинной палиндромной подстроки за линейное время, получено 01.10.2016. Объяснение и реализация алгоритма линейного времени Манакера на Python.
• Jeuring, Йохан (2007-2010), палиндромы, извлекаются 2011-11-22. Реализация алгоритма линейного времени Джеуринга на языке Haskell.
• Палиндромы. Реализация алгоритма линейного времени Манахера на Java.

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