Databases
StackOverflow2013
Postsdbo
POManacher's algorithm (algorithm to find longest palindrome substring in linear time)
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POManacher's algorithm (algorithm to find longest palindrome substring in linear time)
    primarykey
    data
    text
    <p>After spending about 6-8 hours trying to digest the Manacher's algorithm, I am ready to throw in the towel. But before I do, here is one last shot in the dark: can anyone explain it? I don't care about the code. I want somebody to explain the <strong>ALGORITHM</strong>.</p> <p>Here seems to be a place that others seemed to enjoy in explaining the algorithm: <a href="http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html">http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html</a></p> <p>I understand why you would want to transform the string, say, 'abba' to #a#b#b#a# After than I'm lost. For example, the author of the previously mentioned website says the key part of the algorithm is: </p> <pre><code> if P[ i' ] ≤ R – i, then P[ i ] ← P[ i' ] else P[ i ] ≥ P[ i' ]. (Which we have to expand past the right edge (R) to find P[ i ]) </code></pre> <p>This seems wrong, because he/she says at one point that P[i] equals 5 when P[i'] = 7 and P[i] is not less or equal to R - i. </p> <p>If you are not familiar with the algorithm, here are some more links: <a href="http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html">http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html</a> (I've tried this one, but the terminology is awful and confusing. First, some things are not defined. Also, too many variables. You need a checklist to recall what variable is referring to what.)</p> <p>Another is: <a href="http://www.akalin.cx/longest-palindrome-linear-time">http://www.akalin.cx/longest-palindrome-linear-time</a> (good luck)</p> <p>The basic gist of the algorithm is to find the longest palindrome in linear time. It can be done in O(n^2) with a minimum to medium amount of effort. This algorithm is supposed to be quite "clever" to get it down to O(n). </p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USSaeed Amiri
    1. USuser678392
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POManacher's algorithm (algorithm to find longest palindrome substring in linear time)
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POManacher's algorithm (algorithm to find longest palindrome substring in linear time)
      1. USJustinDanielson
      1. VTFavorite
    3. VO
      singulars
      1. POManacher's algorithm (algorithm to find longest palindrome substring in linear time)
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThis isn't an answer, but a suggestion. I find one of the best techniques to figure something like a difficult algorithm out is to explain it to someone else, even if you do not fully understand it. So just set some poor sap down and explain the algorithm to them. By the time that you're done, your subject should be annoyed with you, but you should have a far greater grasp on the algorithm.
      singulars
      1. POManacher's algorithm (algorithm to find longest palindrome substring in linear time)
      1. USOmnipotentEntity
    2. COI've tried something like that. I sat down and tried to write down the algorithm "in my own words". That helped tremendously. But I haven't gotten any farther. (Also, there are no poor saps around.) Thanks though, will keep the suggestion in mind.
      singulars
      1. POManacher's algorithm (algorithm to find longest palindrome substring in linear time)
      1. USuser678392
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload