title: Manacher's algorithm (algorithm to find longest palindrome substring in linear time)
body: <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>