Longest palindromic substring (original) (raw)
最长回文子串（英語：Longest palindromic substring）是计算机科学中的問題，在一个字符串中查找一个最长的连续的回文的子串，例如“banana”最长回文子串是“anana”。最长回文子串并不一定是唯一的，比如在“abracadabra”中，没有超过3个字符的回文子串，但是有两个回文字串长度都是3：“ada”和“aca”。在一些应用中，我们求出全部的极大回文子串（不被其他回文串包含的回文子串）。 Glenn Manacher 于1975年发现了一种线性时间算法，可以在列出给定字符串中从任意位置开始的所有回文子串。并且，Apostolico, Breslauer & Galil 发现，同样的算法也可以在任意位置查找全部极大回文子串，并且时间复杂度是线性的。因此，他们提供了一种时间复杂度为线性的最长回文子串解法。另外，Jeuring (1994), Gusfield (1997)发现了基于后缀树的算法。也存在已知的高效并行算法。 最长回文子串算法不应当与最长回文子序列算法混淆。
| Property | Value |
|---|---|
| dbo:abstract | In computer science, the longest palindromic substring or longest symmetric factor problem is the problem of finding a maximum-length contiguous substring of a given string that is also a palindrome. For example, the longest palindromic substring of "bananas" is "anana". The longest palindromic substring is not guaranteed to be unique; for example, in the string "abracadabra", there is no palindromic substring with length greater than three, but there are two palindromic substrings with length three, namely, "aca" and "ada". In some applications it may be necessary to return all maximal palindromic substrings (that is, all substrings that are themselves palindromes and cannot be extended to larger palindromic substrings) rather than returning only one substring or returning the maximum length of a palindromic substring. invented an -time algorithm for listing all the palindromes that appear at the start of a given string of length . However, as observed e.g., by , the same algorithm can also be used to find all maximal palindromic substrings anywhere within the input string, again in time. Therefore, it provides an -time solution to the longest palindromic substring problem. Alternative -time solutions were provided by , and by , who described a solution based on suffix trees. A faster algorithm can be achieved in the word RAM model of computation if the size of the input alphabet is in . In particular, this algorithm runs in time using space. Efficient parallel algorithms are also known for the problem. The longest palindromic substring problem should not be confused with the different problem of finding the longest palindromic subsequence. (en) В разделе компьютерные науки, задача о самой длинной палиндромиальной подстроке — это задача отыскания самой длинной подстроки данной строки являющейся палиндромом. Например, самая длинная палиндромиальная подстрока «банана» это «анана». Самая длинная палиндромиальная подстрока не обязательно единственна; например в строке «абракадабра» нет палиндромиальной подстроки длиннее трёх символов, но есть состоящие в точности из трёх символов, а именно, «ака» и «ада». В некоторых приложениях требуется найти все максимальные палиндромиальные подстроки (а именно, все подстроки, которые сами по себе являются палиндромами и не могут быть дополнены до более длинных палиндромиальных подстрок) вместо того чтобы вернуть только одну подстроку или вернуть максимальную длину палиндромиальной подстроки. ) изобрёл линейный по времени алгоритм перечисления всех палиндромов находящихся в начале данной строки. Однако, как было показано ), этот же алгоритм может быть использован для нахождения всех самых длинных палиндромиальных подстрок в любом месте данной строки, опять-таки за линейное время. Поэтому он обеспечивает решение задачи нахождения максимальной палиндромиальной подстроки за линейное время. Альтернативные решения, работающие за линейное время, были предложены ), и ), который описал решение основанное на использовании суффиксных деревьев. Также известны эффективные параллельные алгоритмы решения этой задачи. Задачу нахождения самой длинной палиндромиальной подстроки не следует путать с задачей нахождения самой длинной палиндромиальной . (ru) 最长回文子串（英語：Longest palindromic substring）是计算机科学中的問題，在一个字符串中查找一个最长的连续的回文的子串，例如“banana”最长回文子串是“anana”。最长回文子串并不一定是唯一的，比如在“abracadabra”中，没有超过3个字符的回文子串，但是有两个回文字串长度都是3：“ada”和“aca”。在一些应用中，我们求出全部的极大回文子串（不被其他回文串包含的回文子串）。 Glenn Manacher 于1975年发现了一种线性时间算法，可以在列出给定字符串中从任意位置开始的所有回文子串。并且，Apostolico, Breslauer & Galil 发现，同样的算法也可以在任意位置查找全部极大回文子串，并且时间复杂度是线性的。因此，他们提供了一种时间复杂度为线性的最长回文子串解法。另外，Jeuring (1994), Gusfield (1997)发现了基于后缀树的算法。也存在已知的高效并行算法。 最长回文子串算法不应当与最长回文子序列算法混淆。 (zh) |
| dbo:wikiPageExternalLink | https://creativecommons.org/licenses/by/3.0/ https://articles.leetcode.com/longest-palindromic-substring-part-ii/%7Ctitle=Longest https://www.akalin.com/longest-palindrome-linear-time%7Ctitle=Finding https://web.archive.org/web/20180629091030/http:/wcipeg.com/wiki/index.php%3Ftitle=Longest_palindromic_substring https://web.archive.org/web/20181208031518/https:/articles.leetcode.com/longest-palindromic-substring-part-ii/%7Carchive-date=2018-12-08 https://docs.lib.purdue.edu/cgi/viewcontent.cgi%3Farticle=2068&context=cstech https://doi.org/10.4230/LIPIcs.CPM.2022.20 https://github.com/vvikas/palindromes/blob/master/src/LongestPalindromicSubString.java%7Ctitle=Palindromes http://www.staff.science.uu.nl/~jeuri101/homepage/palindromes/index.html%7Ctitle=Palindromes%7Cdate=2007%E2%80%932010%7Caccessdate=2011-11-22 |
| dbo:wikiPageID | 33593580 (xsd:integer) |
| dbo:wikiPageLength | 17379 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122997955 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Subsequence dbr:Computer_science dbr:Parallel_algorithm dbr:Suffix_tree dbr:Theoretical_Computer_Science_(journal) dbc:Problems_on_strings dbr:Journal_of_the_ACM dbc:Palindromes dbr:Palindrome dbr:Word_RAM dbr:Substring |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Cn dbt:Harvtxt dbt:Reflist |
| dcterms:subject | dbc:Problems_on_strings dbc:Palindromes |
| gold:hypernym | dbr:Problem |
| rdf:type | yago:WikicatPalindromes yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:LanguageUnit106284225 yago:Palindrome106294828 yago:Part113809207 yago:Problem114410605 yago:Relation100031921 yago:Word106286395 dbo:Disease yago:State100024720 yago:WikicatProblemsOnStrings |
| rdfs:comment | 最长回文子串（英語：Longest palindromic substring）是计算机科学中的問題，在一个字符串中查找一个最长的连续的回文的子串，例如“banana”最长回文子串是“anana”。最长回文子串并不一定是唯一的，比如在“abracadabra”中，没有超过3个字符的回文子串，但是有两个回文字串长度都是3：“ada”和“aca”。在一些应用中，我们求出全部的极大回文子串（不被其他回文串包含的回文子串）。 Glenn Manacher 于1975年发现了一种线性时间算法，可以在列出给定字符串中从任意位置开始的所有回文子串。并且，Apostolico, Breslauer & Galil 发现，同样的算法也可以在任意位置查找全部极大回文子串，并且时间复杂度是线性的。因此，他们提供了一种时间复杂度为线性的最长回文子串解法。另外，Jeuring (1994), Gusfield (1997)发现了基于后缀树的算法。也存在已知的高效并行算法。 最长回文子串算法不应当与最长回文子序列算法混淆。 (zh) In computer science, the longest palindromic substring or longest symmetric factor problem is the problem of finding a maximum-length contiguous substring of a given string that is also a palindrome. For example, the longest palindromic substring of "bananas" is "anana". The longest palindromic substring is not guaranteed to be unique; for example, in the string "abracadabra", there is no palindromic substring with length greater than three, but there are two palindromic substrings with length three, namely, "aca" and "ada". In some applications it may be necessary to return all maximal palindromic substrings (that is, all substrings that are themselves palindromes and cannot be extended to larger palindromic substrings) rather than returning only one substring or returning the maximum len (en) В разделе компьютерные науки, задача о самой длинной палиндромиальной подстроке — это задача отыскания самой длинной подстроки данной строки являющейся палиндромом. Например, самая длинная палиндромиальная подстрока «банана» это «анана». Самая длинная палиндромиальная подстрока не обязательно единственна; например в строке «абракадабра» нет палиндромиальной подстроки длиннее трёх символов, но есть состоящие в точности из трёх символов, а именно, «ака» и «ада». В некоторых приложениях требуется найти все максимальные палиндромиальные подстроки (а именно, все подстроки, которые сами по себе являются палиндромами и не могут быть дополнены до более длинных палиндромиальных подстрок) вместо того чтобы вернуть только одну подстроку или вернуть максимальную длину палиндромиальной подстроки. (ru) |
| rdfs:label | Longest palindromic substring (en) Поиск длиннейшей подстроки-палиндрома (ru) 最长回文子串 (zh) |
| owl:sameAs | freebase:Longest palindromic substring yago-res:Longest palindromic substring wikidata:Longest palindromic substring dbpedia-ru:Longest palindromic substring dbpedia-sr:Longest palindromic substring dbpedia-zh:Longest palindromic substring https://global.dbpedia.org/id/4rE5D |
| prov:wasDerivedFrom | wikipedia-en:Longest_palindromic_substring?oldid=1122997955&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Longest_palindromic_substring |
| is dbo:wikiPageRedirects of | dbr:Manacher's_algorithm |
| is dbo:wikiPageWikiLink of | dbr:Optimal_substructure dbr:Suffix_tree dbr:Longest_common_substring_problem dbr:Palindrome dbr:Palindrome_tree dbr:Manacher's_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Longest_palindromic_substring |