Editing Longest palindromic substring
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 2: | Line 2: | ||
The '''longest palindromic substring''' problem is exactly as it sounds: the problem of finding a maximal-length [[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-length palindromic substrings, in some, only one, and in some, only the maximum length itself. This article discusses algorithms for solving these problems. | The '''longest palindromic substring''' problem is exactly as it sounds: the problem of finding a maximal-length [[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-length palindromic substrings, in some, only one, and in some, only the maximum length itself. This article discusses algorithms for solving these problems. | ||
+ | |||
+ | ambien cr online ordering ambien online ambien next day delivery <a href=>non prescription ambien</a>. ambian 10mg how long does it take for ambien to kick in best generic ambien ambien dosages . ambien uk ambien from india . ambien no prescription buy zolpidem online canada tablet zolpidem generic name ambien zolpidem from india sleeping pill ambien | ||
==Toward a better bound== | ==Toward a better bound== | ||
Line 75: | Line 77: | ||
<ref name="ukkonen">E. Ukkonen. (1995). On-line construction of suffix trees. ''Algorithmica'' '''14'''(3):249-260. [http://www.cs.helsinki.fi/u/ukkonen/SuffixT1.pdf PDF] | [http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf PDF with figures]</ref> | <ref name="ukkonen">E. Ukkonen. (1995). On-line construction of suffix trees. ''Algorithmica'' '''14'''(3):249-260. [http://www.cs.helsinki.fi/u/ukkonen/SuffixT1.pdf PDF] | [http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf PDF with figures]</ref> | ||
<ref name="tarjan">Gabow, H. N.; Tarjan, R. E. (1983), "A linear-time algorithm for a special case of disjoint set union", <i>Proceedings of the 15th ACM Symposium on Theory of Computing (STOC)</i>, pp. 246–251, doi:[http://dx.doi.org/10.1145%2F800061.808753 10.1145/800061.808753]</ref> | <ref name="tarjan">Gabow, H. N.; Tarjan, R. E. (1983), "A linear-time algorithm for a special case of disjoint set union", <i>Proceedings of the 15th ACM Symposium on Theory of Computing (STOC)</i>, pp. 246–251, doi:[http://dx.doi.org/10.1145%2F800061.808753 10.1145/800061.808753]</ref> | ||
− | <ref name="akalin"> | + | <ref name="akalin">Frederick Akalin. Finding the longest palindromic substring in linear time. Retrieved 2010-11-13 from [http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/ http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/]. ''(This source contains a Python implementation of the simple linear-time algorithm.)''</ref> |
<ref name="manacher">Glenn Manacher. 1975. A New Linear-Time "On-Line" Algorithm for Finding the Smallest Initial Palindrome of a String. J. ACM 22, 3 (July 1975), 346-351. DOI=10.1145/321892.321896 http://doi.acm.org/10.1145/321892.321896 </ref> | <ref name="manacher">Glenn Manacher. 1975. A New Linear-Time "On-Line" Algorithm for Finding the Smallest Initial Palindrome of a String. J. ACM 22, 3 (July 1975), 346-351. DOI=10.1145/321892.321896 http://doi.acm.org/10.1145/321892.321896 </ref> | ||
<ref name="galil">Alberto Apostolico, Dany Breslauer, and Zvi Galil (1994), "Parallel Detection of all Palindromes in a String", Comput. Sci.</ref> | <ref name="galil">Alberto Apostolico, Dany Breslauer, and Zvi Galil (1994), "Parallel Detection of all Palindromes in a String", Comput. Sci.</ref> | ||
Line 88: | Line 90: | ||
** {{SPOJ|PALIM|Yet Another Longest Palindrome Problem}} | ** {{SPOJ|PALIM|Yet Another Longest Palindrome Problem}} | ||
** {{SPOJ|PALDR|Even Palindrome}} | ** {{SPOJ|PALDR|Even Palindrome}} | ||
− | * The problem Calf Flac from [http://train.usaco.org/ the USACO training pages] can be solved using the naive algorithm. | + | * The problem Calf Flac from [http://train.usaco.org/ the USACO training pages] can be solved using the naive algorithm. |