5 ms·

Does anyone know why the suffix tree algorithm is the one commonly shown as the solution to finding the longest palindrome? Manacher's algorithm is conceptuall

Does anyone know why the suffix tree algorithm is the one commonly shown as the solution to finding the longest palindrome? Manacher's algorithm is conceptually simpler, has better performance and memory demands, and isn't new (the original paper is from 1975).

mjn 15y ago
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.html http://johanjeuring.blogspot.com/2007/08/finding-palindromes...), which turned into some software (http://www.staff.science.uu.nl/~jeuri101/homepage/palindromes/ 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 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 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.
bbi5291 15y ago
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.
- dhruvbird 15y ago
  I should thank you for the brilliantly written article. All the claims have been mentioned clearly, and the reasoning strung together in a coherent manner. I agree with the fact that getting the optimization isn't intuitive, but the basic O(n^2) on which the idea is based is almost trivial.

mjn 15y ago

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.html http://johanjeuring.blogspot.com/2007/08/finding-palindromes...), which turned into some software (http://www.staff.science.uu.nl/~jeuri101/homepage/palindromes/ 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 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 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.

bbi5291 15y ago

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.

dhruvbird 15y ago
I should thank you for the brilliantly written article. All the claims have been mentioned clearly, and the reasoning strung together in a coherent manner. I agree with the fact that getting the optimization isn't intuitive, but the basic O(n^2) on which the idea is based is almost trivial.