Editing Longest palindromic substring

Jump to: navigation, search

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 38: Line 38:
 
However, there exists a simpler, shorter, faster, less memory-hungry algorithm<ref name="akalin"/> which accesses the string only by comparing its characters for equality (and hence has running time independent of alphabet size). This is known as ''Manacher's algorithm''.<ref name="manacher"/><ref name="galil"/> Again we will compute the longest palindromic substring centered around each possible position (so that returning all longest palindromic substrings is as easy as simply finding the maximum possible length for a palindromic substring). Our algorithm will return a ''longest palindrome array'': an array in which the <math>i</math><sup>th</sup> element contains the length of the longest palindrome centered around the <math>i</math><sup>th</sup> position from the left. (Note that the parities of elements in the longest palindrome array alternate.)
 
However, there exists a simpler, shorter, faster, less memory-hungry algorithm<ref name="akalin"/> which accesses the string only by comparing its characters for equality (and hence has running time independent of alphabet size). This is known as ''Manacher's algorithm''.<ref name="manacher"/><ref name="galil"/> Again we will compute the longest palindromic substring centered around each possible position (so that returning all longest palindromic substrings is as easy as simply finding the maximum possible length for a palindromic substring). Our algorithm will return a ''longest palindrome array'': an array in which the <math>i</math><sup>th</sup> element contains the length of the longest palindrome centered around the <math>i</math><sup>th</sup> position from the left. (Note that the parities of elements in the longest palindrome array alternate.)
  
The algorithm processes the string from left to right, and fills in the longest palindrome array in the same order, so that when any given position is being considered, the longest palindromes centered around all positions to the left are already known. The algorithm distinguishes two kinds of positions: "interesting" positions and "uninteresting" positions. The algorithm "hops" from each interesting position to the one immediately to the right. It spends amortized constant time on each interesting position. Interesting positions are so named because any maximal-length palindromic substring overall must be centered at one of them. Uninteresting positions' entries in the longest palindrome array can be computed in constant time "in passing" from one interesting position to the next.
+
The algorithm processes the string from left to right, and fills in the longest palindrome array in the same order, so that when any given position is being considered, the longest palindromes centered around all positions to the left are already known. The algorithm distinguishes two kinds of positions: "interesting" positions and "uninteresting" positions. The algorithm "hops" from each interesting position to the one immediately to the right. It spends amortized constant time on each interesting position. Interesting positions are so named because any maximal-length palindromic substring overall must be centered at one of them. Uninteresting positions' entries in the longest palindrome array can be computed in in constant time "in passing" from one interesting position to the next.
  
 
We will proceed through a series of observations to derive the algorithm. First, the designation of interesting and uninteresting positions is not unique; in particular, any uninteresting position can be relabelled interesting without affecting correctness or consistency. That being said, we begin by denoting the first position --- the one immediately to the left of the first character --- interesting, and going from there.
 
We will proceed through a series of observations to derive the algorithm. First, the designation of interesting and uninteresting positions is not unique; in particular, any uninteresting position can be relabelled interesting without affecting correctness or consistency. That being said, we begin by denoting the first position --- the one immediately to the left of the first character --- interesting, and going from there.

Please note that all contributions to PEGWiki are considered to be released under the Attribution 3.0 Unported (see PEGWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel | Editing help (opens in new window)

Templates used on this page: