Re:O(n) algorithm to find longest palindromic substring w/o ...
by mjn on Sunday April 08, 2012 @08:40PM
(#3815381)
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).
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.
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.