O(n) algorithm to find longest palindromic substring w/o suffix trees

My guess is because suffix trees are covered in data-structures courses, and then finding palindromes comes up as a possible application. Whereas Manacher's algorithm is pretty specifically a palindrome-finding algorithm, so people only know about it if they're looking for palindrome-finding algorithms in particular (as opposed to example applications of data structures).

Although, it and variants have gotten some web press. A 2007 blog post was much passed around (http://johanjeuring.blogspot.com/2007/08/finding-palindromes...), which turned into some software (http://www.staff.science.uu.nl/~jeuri101/homepage/palindrome...). There's also a good exposition, and Python code, in another 2007 blog post (http://www.akalin.cx/longest-palindrome-linear-time).

I used the latter code to scan a local mirror of Project Gutenberg for word-unit palindromes, which are palindromes where words rather than letters are the units (http://www.kmjn.org/notes/word_unit_palindromes.html), which I why I know about it. It actually works for that with minimal modification, since it can operate on any Python sequence, not just strings.

I think the answer to this is that the suffix tree algorithm is conceptually simpler if you already know suffix trees. Personally, I find Manacher's algorithm very difficult to intuit (and I'm the one who wrote the article in this post in the first place). Its better performance is indisputable, though.

Yes, for instance in genetics:

http://johanjeuring.blogspot.com/2007/08/finding-palindromes...

Quoting the article: "Every palindromic substring has a centre. For an odd-length substring, this is its middle character; for an even-length substring, this is the imaginary space between its two middle characters. Call each character and each space in the original string a position. Then there are 2N+1 positions in any string of length N (to simplify things later on, we assume there is a position just before the first character and one just after the last), and any longest palindromic substring must have one of these as its centre."

From Google Cache, this one exploits the theorem (which the page proves) that the longest palindromic substring of a string S is the longest common substring between S and its reversal S'. Since there are linear-time longest-common-substring algorithms, finding longest palindromes therefore is linear time. It doesn't actually say which LCS algorithm they'd use, since the page is more about the proof. They even admit that it probably isn't the best approach in practice.

Nope, see the section "A simple asymptotically optimal solution" - it doesn't use Suffix Arrays.