Manacher's Algorithm – Longest Palindromic Substring
A slower O(nlog(n)) but IMO much simpler algorithm is to just using a rolling hash[1]. With linear time precomputation you can compute the hash of any substring range in constant time.
Then for each position, you can just binary search for the longest palindrome centered at that position.
If you don't get the explanation in the article, one of the multiple alternate explanations or corrections at http://stackoverflow.com/questions/10468208/manachers-algori... might suffice instead.
People, please. This presents a problem poignantly and provides a pleasant programmatic solution - the precise point of "hacker news". Be not so butt-bothered about non-apparent algorithm applications.
Wording is a bit sloppy: "Extending R (the inner while loop) takes at most a total of N steps, and positioning and testing each centers take a total of N steps too. Therefore, this algorithm guarantees to finish in at most 2*N steps, giving a linear time solution."
What he means is that the total time taken by ALL executions of the inner loop combined is at most N, not that each run of the inner loop takes at most N steps (otherwise it would become quadratic).
If you like this, Manacher's algo is very similar to z-string matching algo: http://codeforces.com/blog/entry/3107
its funny its on HN. I just got asked this question in an tech interview last week..
Are there any applications for this?
Finding palindromes in C strings. The most important problem in computer science. If software engineering job interviews are to be believed.