Edit Question - KnowledgeHub

Title Body

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 ALGORITHM . Here seems to be a place that others seemed to enjoy in explaining the algorithm: http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html 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: 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 ]) 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. If you are not familiar with the algorithm, here are some more links: http://tristan-interview.blogspot.com/2011/11/longest-palindrome-substring-manachers.html (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.) Another is: http://www.akalin.cx/longest-palindrome-linear-time (good luck) 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).

Tags (comma-separated) Cancel