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

Patarakin в 14:50, 28 сентября 2023

2023-09-28T14:50:58Z

← Предыдущая версия		Версия от 17:50, 28 сентября 2023
Строка 1:		Строка 1:
	В разделе [[компьютерные науки]], задача '''о самой длинной палиндромиальной подстроке''' — это задача отыскания самой длинной подстроки данной строки являющейся [[палиндром]]ом. Например, самая длинная палиндромиальная подстрока «банана» это «анана». Самая длинная палиндромиальная подстрока не обязательно единственна; например в строке «абракадабра» нет палиндромиальной подстроки длиннее трёх символов, но есть состоящие в точности из трёх символов, а именно, «ака» и «ада». В некоторых приложениях требуется найти все максимальные палиндромиальные подстроки (а именно, все подстроки, которые сами по себе являются палиндромами и не могут быть дополнены до более длинных палиндромиальных подстрок) вместо того чтобы вернуть только одну подстроку или вернуть максимальную длину палиндромиальной подстроки.		В разделе [[компьютерные науки]], задача '''о самой длинной палиндромиальной подстроке''' — это задача отыскания самой длинной подстроки данной строки являющейся [[палиндром]]ом. Например, самая длинная палиндромиальная подстрока «банана» это «анана». Самая длинная палиндромиальная подстрока не обязательно единственна; например в строке «абракадабра» нет палиндромиальной подстроки длиннее трёх символов, но есть состоящие в точности из трёх символов, а именно, «ака» и «ада». В некоторых приложениях требуется найти все максимальные палиндромиальные подстроки (а именно, все подстроки, которые сами по себе являются палиндромами и не могут быть дополнены до более длинных палиндромиальных подстрок) вместо того чтобы вернуть только одну подстроку или вернуть максимальную длину палиндромиальной подстроки.

	~~{{harvtxt\|~~Manacher~~\|1975}}~~ изобрёл линейный по времени алгоритм перечисления всех палиндромов находящихся в начале данной строки. Однако, как было показано {{harvtxt\|Apostolico\|Breslauer\|Galil\|1995}}, этот же алгоритм может быть использован для нахождения всех самых длинных палиндромиальных подстрок в любом месте данной строки, опять-таки за линейное время. Поэтому он обеспечивает решение задачи нахождения максимальной палиндромиальной подстроки за линейное время. Альтернативные решения, работающие за линейное время, были предложены {{harvtxt\|Jeuring\|1994}}, и {{harvtxt\|Gusfield\|1997}}, который описал решение основанное на использовании [[Суффиксное дерево\|суффиксных деревьев]]. Также известны эффективные параллельные алгоритмы решения этой задачи.<ref>{{harvtxt\|Crochemore\|Rytter\|1991}}, {{harvtxt\|Apostolico\|Breslauer\|Galil\|1995}}.</ref>		Manacher изобрёл линейный по времени алгоритм перечисления всех палиндромов находящихся в начале данной строки. Однако, как было показано {{harvtxt\|Apostolico\|Breslauer\|Galil\|1995}}, этот же алгоритм может быть использован для нахождения всех самых длинных палиндромиальных подстрок в любом месте данной строки, опять-таки за линейное время. Поэтому он обеспечивает решение задачи нахождения максимальной палиндромиальной подстроки за линейное время. Альтернативные решения, работающие за линейное время, были предложены {{harvtxt\|Jeuring\|1994}}, и {{harvtxt\|Gusfield\|1997}}, который описал решение основанное на использовании [[Суффиксное дерево\|суффиксных деревьев]]. Также известны эффективные параллельные алгоритмы решения этой задачи.<ref>{{harvtxt\|Crochemore\|Rytter\|1991}}, {{harvtxt\|Apostolico\|Breslauer\|Galil\|1995}}.</ref>

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

	== Алгоритм Манакера ==		== Алгоритм Манакера ==
	~~{{Основная статья\|Алгоритм Манакера}}~~
	Чтобы за линейное время найти в строке самый длинный палиндром, алгоритм может воспользоваться следующими свойствами палиндромов и подпалиндромов:		Чтобы за линейное время найти в строке самый длинный палиндром, алгоритм может воспользоваться следующими свойствами палиндромов и подпалиндромов:
	# Левая часть палиндрома является зеркальным отражением его правой части		# Левая часть палиндрома является зеркальным отражением его правой части

Patarakin в 14:50, 28 сентября 2023

2023-09-28T14:50:17Z

← Предыдущая версия		Версия от 17:50, 28 сентября 2023
Строка 74:		Строка 74:

	</source>		</source>

	~~== Примечания ==~~
	~~{{примечания}}~~

	~~== Литература ==~~
	* {{citation
	~~\| last1 = Apostolico \| first1 = Alberto~~
	~~\| last2 = Breslauer \| first2 = Dany~~
	~~\| last3 = Galil \| first3 = Zvi \| author3-link = Zvi Galil~~
	~~\| title = Parallel detection of all palindromes in a string~~
	~~\| journal = [[Theoretical Computer Science (journal)\|Theoretical Computer Science]]~~
	~~\| volume = 141~~
	~~\| issue = 1–2~~
	~~\| year = 1995~~
	~~\| doi = 10.1016/0304-3975(94)00083-U~~
	~~\| pages = 163–173}}.~~
	* {{citation
	~~\| last1 = Crochemore \| first1 = Maxime~~
	~~\| last2 = Rytter \| first2 = Wojciech \| author2-link = Wojciech Rytter~~
	~~\| doi = 10.1016/0304-3975(91)90073-B~~
	~~\| issue = 1~~
	~~\| journal = Theoretical Computer Science~~
	~~\| mr = 1130372~~
	~~\| pages = 59–82~~
	~~\| title = Usefulness of the Karp–Miller–Rosenberg algorithm in parallel computations on strings and arrays~~
	~~\| volume = 88~~
	~~\| year = 1991}}.~~
	* {{citation
	~~\| last1 = Crochemore \| first1 = Maxime~~
	~~\| last2 = Rytter \| first2 = Wojciech \| author2-link = Wojciech Rytter~~
	~~\| title = Jewels of Stringology: Text Algorithms~~
	~~\| publisher = World Scientific~~
	~~\| year = 2003~~
	~~\| isbn = 978-981-02-4897-0~~
	~~\| contribution = 8.1 Searching for symmetric words~~
	~~\| pages = 111–114}}.~~
	* {{citation
	~~\| last = Gusfield \| first = Dan~~
	~~\| contribution = 9.2 Finding all maximal palindromes in linear time~~
	~~\| doi = 10.1017/CBO9780511574931~~
	~~\| isbn = 0-521-58519-8~~
	~~\| location = Cambridge~~
	~~\| mr = 1460730~~
	~~\| pages = 197–199~~
	~~\| publisher = Cambridge University Press~~
	~~\| title = Algorithms on Strings, Trees, and Sequences~~
	~~\| year = 1997}}.~~
	* {{citation
	~~\| last = Jeuring \| first = Johan~~
	~~\| doi = 10.1007/BF01182773~~
	~~\| issue = 2~~
	~~\| journal = Algorithmica~~
	~~\| mr = 1272521~~
	~~\| pages = 146–184~~
	~~\| title = The derivation of on-line algorithms, with an application to finding palindromes~~
	~~\| volume = 11~~
	~~\| year = 1994}}.~~
	* {{citation
	~~\| last = Manacher \| first = Glenn~~
	~~\| doi = 10.1145/321892.321896~~
	~~\| issue = 3~~
	~~\| journal = [[Journal of the ACM]]~~
	~~\| pages = 346–351~~
	~~\| title = A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string~~
	~~\| volume = 22~~
	~~\| year = 1975}}.~~

	~~== Ссылки ==~~
	* {{citation\|url=http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html\|title=Longest Palindromic Substring Part II.\|date=2011-11-20}} {{Wayback\|url=http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html \|date=20140202183655 }}. A description of Manacher’s algorithm for finding the longest palindromic substring in linear time.
	* {{citation\|first=Fred\|last=Akalin\|url=http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/\|title=Finding the longest palindromic substring in linear time\|year=2007\|accessdate=2011-11-22}}. An explanation and Python implementation of Manacher’s linear-time algorithm.
	* {{citation\|first=Johan\|last=Jeuring\|url=http://www.staff.science.uu.nl/~jeuri101/homepage/palindromes/index.html\|title=Palindromes\|date=2007–2010\|accessdate=2011-11-22}}. Haskell implementation of Jeuring’s linear-time algorithm.
	* {{citation\|url=https://github.com/vvikas/palindromes/blob/master/src/LongestPalindromicSubString.java\|title=Palindromes}}{{Недоступная ссылка\|date=Май 2019 \|bot=InternetArchiveBot }}. Java implementation of Manacher’s linear-time algorithm.

	~~[[Категория:Строковые алгоритмы]]~~
	~~[[Категория:Алгоритмы поиска]]~~
	~~[[Категория:Палиндром]]~~

	: ''This article incorporates text from [https://web.archive.org/web/20150128113452/http://wcipeg.com/wiki/index.php?title=Longest_palindromic_substring Longest palindromic substring] on PEGWiki under a Creative Commons Attribution ([http://creativecommons.org/licenses/by/3.0/ CC-BY-3.0]) license.''

Patarakin: 1 версия импортирована

2022-10-19T17:55:02Z

1 версия импортирована

← Предыдущая версия	Версия от 20:55, 19 октября 2022
(нет различий)

ru_wikipedia>Lumaca: Добавлена Категория:Палиндром с помощью HotCat

2022-07-23T11:11:23Z

Добавлена Категория:Палиндром с помощью HotCat

Новая страница

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

{{harvtxt|Manacher|1975}} изобрёл линейный по времени алгоритм перечисления всех палиндромов находящихся в начале данной строки. Однако, как было показано {{harvtxt|Apostolico|Breslauer|Galil|1995}}, этот же алгоритм может быть использован для нахождения всех самых длинных палиндромиальных подстрок в любом месте данной строки, опять-таки за линейное время. Поэтому он обеспечивает решение задачи нахождения максимальной палиндромиальной подстроки за линейное время. Альтернативные решения, работающие за линейное время, были предложены {{harvtxt|Jeuring|1994}}, и {{harvtxt|Gusfield|1997}}, который описал решение основанное на использовании [[Суффиксное дерево|суффиксных деревьев]]. Также известны эффективные параллельные алгоритмы решения этой задачи.<ref>{{harvtxt|Crochemore|Rytter|1991}}, {{harvtxt|Apostolico|Breslauer|Galil|1995}}.</ref>

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

== Алгоритм Манакера ==
{{Основная статья|Алгоритм Манакера}}
Чтобы за линейное время найти в строке самый длинный палиндром, алгоритм может воспользоваться следующими свойствами палиндромов и подпалиндромов:
# Левая часть палиндрома является зеркальным отражением его правой части
# (Случай 1) Третий палиндром, чей центр лежит в правой части первого палиндрома, будет иметь в точности ту же длину, что и второй палиндром, центр которого зеркально отражен в левую часть, если второй палиндром лежит внутри первого, отступая от границы по крайней мере на один символ.
# (Случай 2) Если второй палиндром имеет общую границу с первым палиндромом, или простирается за его пределы, то длина третьего палиндрома гарантировано не меньше расстояния от его центра до правой границы первого палиндрома. Эта длина совпадает с расстоянием от центра второго палиндрома до самого левого символа первого палиндрома.
# Чтобы найти длину третьего палиндрома в случае 2, необходимо сравнивать символы, идущие за самым правым символом первого палиндрома с их зеркальным отражением относительно центра третьего палиндрома пока либо не исчерпается строка, либо не будет обнаружено неравенство символов.
# (Случай 3) Ни первый, ни второй палиндромы не предоставляют информации, позволяющей определить длину четвёртого палиндрома, чей центр лежит за границей первого палиндрома.
# Поэтому для определения слева направо палиндромиальных длин подстрок в строке желательно иметь опорный палиндром (исполняющий роль первого палиндрома), чьи символы занимают самые правые положения в строке (и, следовательно, третий палиндром в случае 2 и четвёртый палиндром в случае 3 могут заменять первый палиндром, чтобы стать новым опорным палиндромом).
# Что касается оценки времени определения палиндромиальный длины для каждого символа строки: в Случае 1 сравнения символов не производится, в Случаях 2 и 3 кандидатами для сравнения являются только символы строки, лежащей за самым правым символом опорного палиндрома (и следовательно Случай 3 всегда приводит к смене опорного палиндрома, когда Случай 2 меняет опорный палиндром только если оказывается что длина третьего палиндрома в действительности больше чем его обещанная минимальная длина).
# Для палиндромов чётной степени центр лежит между двумя центральными символами палиндрома.

=== Реализация ===
Пусть:
* 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))

Результат:
Максимально длинный палиндром, либо первый символ строки

<source lang="cpp">
#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);
}

</source>

== Примечания ==
{{примечания}}

== Литература ==
* {{citation
| last1 = Apostolico | first1 = Alberto
| last2 = Breslauer | first2 = Dany
| last3 = Galil | first3 = Zvi | author3-link = Zvi Galil
| title = Parallel detection of all palindromes in a string
| journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
| volume = 141
| issue = 1–2
| year = 1995
| doi = 10.1016/0304-3975(94)00083-U
| pages = 163–173}}.
* {{citation
| last1 = Crochemore | first1 = Maxime
| last2 = Rytter | first2 = Wojciech | author2-link = Wojciech Rytter
| doi = 10.1016/0304-3975(91)90073-B
| issue = 1
| journal = Theoretical Computer Science
| mr = 1130372
| pages = 59–82
| title = Usefulness of the Karp–Miller–Rosenberg algorithm in parallel computations on strings and arrays
| volume = 88
| year = 1991}}.
* {{citation
| last1 = Crochemore | first1 = Maxime
| last2 = Rytter | first2 = Wojciech | author2-link = Wojciech Rytter
| title = Jewels of Stringology: Text Algorithms
| publisher = World Scientific
| year = 2003
| isbn = 978-981-02-4897-0
| contribution = 8.1 Searching for symmetric words
| pages = 111–114}}.
* {{citation
| last = Gusfield | first = Dan
| contribution = 9.2 Finding all maximal palindromes in linear time
| doi = 10.1017/CBO9780511574931
| isbn = 0-521-58519-8
| location = Cambridge
| mr = 1460730
| pages = 197–199
| publisher = Cambridge University Press
| title = Algorithms on Strings, Trees, and Sequences
| year = 1997}}.
* {{citation
| last = Jeuring | first = Johan
| doi = 10.1007/BF01182773
| issue = 2
| journal = Algorithmica
| mr = 1272521
| pages = 146–184
| title = The derivation of on-line algorithms, with an application to finding palindromes
| volume = 11
| year = 1994}}.
* {{citation
| last = Manacher | first = Glenn
| doi = 10.1145/321892.321896
| issue = 3
| journal = [[Journal of the ACM]]
| pages = 346–351
| title = A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string
| volume = 22
| year = 1975}}.

== Ссылки ==
* {{citation|url=http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html|title=Longest Palindromic Substring Part II.|date=2011-11-20}} {{Wayback|url=http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html |date=20140202183655 }}. A description of Manacher’s algorithm for finding the longest palindromic substring in linear time.
* {{citation|first=Fred|last=Akalin|url=http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/|title=Finding the longest palindromic substring in linear time|year=2007|accessdate=2011-11-22}}. An explanation and Python implementation of Manacher’s linear-time algorithm.
* {{citation|first=Johan|last=Jeuring|url=http://www.staff.science.uu.nl/~jeuri101/homepage/palindromes/index.html|title=Palindromes|date=2007–2010|accessdate=2011-11-22}}. Haskell implementation of Jeuring’s linear-time algorithm.
* {{citation|url=https://github.com/vvikas/palindromes/blob/master/src/LongestPalindromicSubString.java|title=Palindromes}}{{Недоступная ссылка|date=Май 2019 |bot=InternetArchiveBot }}. Java implementation of Manacher’s linear-time algorithm.

[[Категория:Строковые алгоритмы]]
[[Категория:Алгоритмы поиска]]
[[Категория:Палиндром]]

: ''This article incorporates text from [https://web.archive.org/web/20150128113452/http://wcipeg.com/wiki/index.php?title=Longest_palindromic_substring Longest palindromic substring] on PEGWiki under a Creative Commons Attribution ([http://creativecommons.org/licenses/by/3.0/ CC-BY-3.0]) license.''

← Предыдущая версия		Версия от 17:50, 28 сентября 2023
Строка 74:		Строка 74:

	</source>		</source>

	~~== Примечания ==~~
	~~{{примечания}}~~

	~~== Литература ==~~
	* {{citation
	~~\| last1 = Apostolico \| first1 = Alberto~~
	~~\| last2 = Breslauer \| first2 = Dany~~
	~~\| last3 = Galil \| first3 = Zvi \| author3-link = Zvi Galil~~
	~~\| title = Parallel detection of all palindromes in a string~~
	~~\| journal = [[Theoretical Computer Science (journal)\|Theoretical Computer Science]]~~
	~~\| volume = 141~~
	~~\| issue = 1–2~~
	~~\| year = 1995~~
	~~\| doi = 10.1016/0304-3975(94)00083-U~~
	~~\| pages = 163–173}}.~~
	* {{citation
	~~\| last1 = Crochemore \| first1 = Maxime~~
	~~\| last2 = Rytter \| first2 = Wojciech \| author2-link = Wojciech Rytter~~
	~~\| doi = 10.1016/0304-3975(91)90073-B~~
	~~\| issue = 1~~
	~~\| journal = Theoretical Computer Science~~
	~~\| mr = 1130372~~
	~~\| pages = 59–82~~
	~~\| title = Usefulness of the Karp–Miller–Rosenberg algorithm in parallel computations on strings and arrays~~
	~~\| volume = 88~~
	~~\| year = 1991}}.~~
	* {{citation
	~~\| last1 = Crochemore \| first1 = Maxime~~
	~~\| last2 = Rytter \| first2 = Wojciech \| author2-link = Wojciech Rytter~~
	~~\| title = Jewels of Stringology: Text Algorithms~~
	~~\| publisher = World Scientific~~
	~~\| year = 2003~~
	~~\| isbn = 978-981-02-4897-0~~
	~~\| contribution = 8.1 Searching for symmetric words~~
	~~\| pages = 111–114}}.~~
	* {{citation
	~~\| last = Gusfield \| first = Dan~~
	~~\| contribution = 9.2 Finding all maximal palindromes in linear time~~
	~~\| doi = 10.1017/CBO9780511574931~~
	~~\| isbn = 0-521-58519-8~~
	~~\| location = Cambridge~~
	~~\| mr = 1460730~~
	~~\| pages = 197–199~~
	~~\| publisher = Cambridge University Press~~
	~~\| title = Algorithms on Strings, Trees, and Sequences~~
	~~\| year = 1997}}.~~
	* {{citation
	~~\| last = Jeuring \| first = Johan~~
	~~\| doi = 10.1007/BF01182773~~
	~~\| issue = 2~~
	~~\| journal = Algorithmica~~
	~~\| mr = 1272521~~
	~~\| pages = 146–184~~
	~~\| title = The derivation of on-line algorithms, with an application to finding palindromes~~
	~~\| volume = 11~~
	~~\| year = 1994}}.~~
	* {{citation
	~~\| last = Manacher \| first = Glenn~~
	~~\| doi = 10.1145/321892.321896~~
	~~\| issue = 3~~
	~~\| journal = [[Journal of the ACM]]~~
	~~\| pages = 346–351~~
	~~\| title = A new linear-time "on-line" algorithm for finding the smallest initial palindrome of a string~~
	~~\| volume = 22~~
	~~\| year = 1975}}.~~

	~~== Ссылки ==~~
	* {{citation\|url=http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html\|title=Longest Palindromic Substring Part II.\|date=2011-11-20}} {{Wayback\|url=http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html \|date=20140202183655 }}. A description of Manacher’s algorithm for finding the longest palindromic substring in linear time.
	* {{citation\|first=Fred\|last=Akalin\|url=http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/\|title=Finding the longest palindromic substring in linear time\|year=2007\|accessdate=2011-11-22}}. An explanation and Python implementation of Manacher’s linear-time algorithm.
	* {{citation\|first=Johan\|last=Jeuring\|url=http://www.staff.science.uu.nl/~jeuri101/homepage/palindromes/index.html\|title=Palindromes\|date=2007–2010\|accessdate=2011-11-22}}. Haskell implementation of Jeuring’s linear-time algorithm.
	* {{citation\|url=https://github.com/vvikas/palindromes/blob/master/src/LongestPalindromicSubString.java\|title=Palindromes}}{{Недоступная ссылка\|date=Май 2019 \|bot=InternetArchiveBot }}. Java implementation of Manacher’s linear-time algorithm.

	~~[[Категория:Строковые алгоритмы]]~~
	~~[[Категория:Алгоритмы поиска]]~~
	~~[[Категория:Палиндром]]~~

	: ''This article incorporates text from [https://web.archive.org/web/20150128113452/http://wcipeg.com/wiki/index.php?title=Longest_palindromic_substring Longest palindromic substring] on PEGWiki under a Creative Commons Attribution ([http://creativecommons.org/licenses/by/3.0/ CC-BY-3.0]) license.''