bbi5291
Re:O(n) algorithm to find longest palindromic substring w/o suffix trees
on Monday April 09, 2012 @12:59AM (#3815891)
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."
Re:O(n) algorithm to find longest palindromic substring w/o suffix trees
on Monday April 09, 2012 @12:55AM (#3815881)
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.