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

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

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

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

Медленный алгоритм [ править ]

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

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

 Longest_Palindrome_SLOW (строка S) { строка S '= S с фиктивным символом (например,' | '), вставленным между каждым символом (включая внешние границы) array PalindromeRadii = [0, ..., 0] // Радиус самого длинного палиндрома с центром в каждом месте в S ' // примечание: длина (S ') = длина (PalindromeRadii) = 2 × длина (S) + 1  Центр = 0 в то время как Центр <длина (S ') { // Определяем самый длинный палиндром, начиная с центра и радиуса и идя к центру + радиус Радиус = 0 в то время как Центр- (Радиус + 1)> = 0 и Центр + (Радиус + 1) <длина (S ') и S' [Центр- (Радиус + 1)] = S '[Центр + (Радиус + 1)] { Радиус = Радиус + 1 }  // Сохраняем радиус самого длинного палиндрома в массиве PalindromeRadii [Центр] = Радиус  Центр = Центр + 1 }   longest_palindrome_in_S '= 2 * макс (PalindromeRadii) +1 longest_palindrome_in_S = (longest_palindrome_in_S'-1) / 2 вернуть longest_palindrome_in_S }

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

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

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

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

 Longest_Palindrome (строка S) { строка S '= S с фиктивным символом (например,' | '), вставленным между каждым символом (включая внешние границы) array PalindromeRadii = [0, ..., 0] // Радиус самого длинного палиндрома с центром в каждом месте в S ' // примечание: длина (S ') = длина (PalindromeRadii) = 2 × длина (S) + 1  Центр = 0 Радиус = 0  в то время как Центр <длина (S ') { // В начале цикла Радиус уже установлен на нижнюю границу самого длинного радиуса. // На первой итерации Radius равен 0, но может быть больше.  // Определяем самый длинный палиндром, начиная с центра и радиуса и идя к центру + радиус в то время как Центр- (Радиус + 1)> = 0 и Центр + (Радиус + 1) <длина (S ') и S' [Центр- (Радиус + 1)] = S '[Центр + (Радиус + 1)] { Радиус = Радиус + 1 }   // Сохраняем радиус самого длинного палиндрома в массиве PalindromeRadii [Центр] = Радиус  // Ниже центр увеличивается. // Если какие-либо предварительно вычисленные значения можно использовать повторно, то они есть. // Также Радиус может быть установлен на значение больше 0  OldCenter = Центр OldRadius = Радиус Центр = Центр + 1 // Значение радиуса по умолчанию будет 0, если мы дойдем до конца следующего цикла.  Радиус = 0  в то время как Center <= OldCenter + OldRadius { // Потому что Центр находится внутри старого палиндрома и каждый символ внутри // палиндром имеет "зеркальный" символ, отраженный в его центре, мы // можно использовать данные, которые были предварительно вычислены для зеркальной точки центра.  MirroredCenter = OldCenter - (Центр - OldCenter) MaxMirroredRadius = OldCenter + OldRadius - Центр если PalindromeRadii [MirroredCenter] <MaxMirroredRadius { PalindromeRadii [Center] = PalindromeRadii [MirroredCenter] Центр = Центр + 1 }  иначе, если PalindromeRadii [MirroredCenter]> MaxMirroredRadius { PalindromeRadii [Center] = MaxMirroredRadius Центр = Центр + 1 }  else { // PalindromeRadii [MirroredCenter] = MaxMirroredRadius Радиус = MaxMirroredRadius break // выйти из цикла раньше времени }  }  }  longest_palindrome_in_S '= 2 * макс (PalindromeRadii) +1 longest_palindrome_in_S = (longest_palindrome_in_S'-1) / 2 вернуть longest_palindrome_in_S }

Особые случаи [ править ]

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

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

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

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

Время выполнения [ править ]

Алгоритм работает за линейное время. Это можно увидеть, установив границы того, сколько итераций выполняется в каждом цикле. Внешний цикл и второй внутренний цикл увеличивают Center на 1 для каждой итерации. Поскольку Center ограничен длиной строки, мы знаем время выполнения этих циклов . Первый внутренний цикл увеличивает радиус на 1 для каждой итерации, а второй внутренний цикл, когда он останавливается, уменьшает радиус не более чем на 1 для каждой итерации. Поскольку второй цикл может выполняться в большинстве случаев, а значение радиуса не может превышать , первый цикл может выполняться в большинстве случаев. Общее время выполнения составляет .${\ displaystyle n}$${\ displaystyle n}$${\ 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 CS1 maint: обескураженный параметр ( ссылка ). Объяснение и реализация алгоритма линейного времени Манакера на Python.
• Jeuring, Йохан (2007-2010), палиндромы , извлекаются 2011-11-22 CS1 maint: discouraged parameter (link). Реализация алгоритма линейного времени Джеуринга на языке Haskell.
• Палиндромы. Реализация алгоритма линейного времени Манахера на Java.

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