Sign up ×

I was Googling about a rather well-known problem, namely: the longest palindromic substring
I have found links that recommend suffix tries as a good solution to the problem.
Example SO and Algos
The approach is (as I understand it) e.g. for a string S create Sr (which is S reversed) and then create a generalized suffix trie.
Then find the longest common sustring of S and Sr which is the path from the root to the deepest node that belongs both to S and Sr.
So the solution using the suffix tries approach essentially reduces to Find the longest common substring problem.
My question is the following:
If the input string is: S = “abacdfgdcaba” so , Sr = “abacdgfdcaba” the longest common substring is abacd which is NOT a palindrome.
So my question is: Is the approach of using suffix tries erroneous? Am i missunderstanding/misreading here?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Yes, finding longest palindrome by using LCS like algorithms is not a good way, I didn't read referenced answer carefully but this line in the answer is completely wrong:


but if you read it and you have a counter example don't worry about it (you are right in 99%), this is common mistake, But simple way is as follow:

Write down the string (barbapapa) as follow: #b#a#r#b#a#p#a#p#a#, now traverse each character of this new string from left to right, check its left and right to check whether it's a palindrome center or not. This algorithm is O(n^2) in worst case and works perfectly correct. but normally will finds palindrome in O(n) (sure proving this in average case is hard). Worst case is in strings with too many long palindromes like aaaaaa...aaaa.

But there is better approach which takes O(n) time, base of this algorithm is by Manacher. Related algorithm is more complicated than what I saw in your referenced answer. But what I offered is base idea of Manacher algorithm, with clever changes in algorithm you can skip checking all left and rights (also there are algorithms by using suffix trees).

P.S: I couldn't see your Algo link because of my internet limitations, I don't know it's correct or not.

I added my discussion with OP to clarify the algorithm:

let test it with barbapapa-> #b#a#r#b#a#p#a#p#a#, start from first #
there is no left so it's center of palindrome with length 1.
Now "b",has # in left and # in right, but there isn't another left to match with right 
so it's a center of palindrome with length 3.
let skip other parts to arrive to first "p":
first left and right is # second left and right is "a", third left and
right is # but forth left and right are not equal so it's center of palindrome
of length 7 #a#p#a# is palindrome but b#a#p#a#p is not 
Now let see first "a" after first "p" you have, #a#p#a#p#a# as palindrome and this "a" 
is center of this palindrome with length 11 if you calculate all other palindromes 
length of all of them are smaller than 11

Also using # is because considering palindromes of even length.

After finding center of palindrome in newly created string, find related palindrom (by knowing the center and its length), then remove # to find out biggest palindrome.

share|improve this answer
also there are algorithms by using suffix trees This part I don't get. Isn't this my OP?I mean if we use suffix tree, it would be in order to find the longest common substring by S and Sr using a generilized suffix tree of S and Sr. So we end up in my original question. So what do you mean here? –  Cratylus May 26 '12 at 17:02
@user384706, Actually I'm not aware how they using suffix tree, I read Manacher's algorithm before, but as I know all of other algorithms are sort of improvements on Manacher algorithm, to make it easier and more useful, I don't think related suffix tree algorithms are using (S,Sr), I'm not sure though. But the answer you mentioned is wrong, Also if you interested more about suffix tree usages in palindromes, You should read related papers (not unsure links), you can find them on my referenced wiki page (if you have an access to download them, I also think you can find them free in the web). –  Saeed Amiri May 26 '12 at 17:07
Why do we need #?I am not clear on how the # helps –  Cratylus May 26 '12 at 18:15
@user384706: for finding palindrome of even length, like: aaaa, which of the as would be center of longest palindrome? none of them, but in a#a#a#a, second # is center of longest palindrome in original string( I wrote sharp in start and end but they are redundant, just for making the word more beautiful;) –  Saeed Amiri May 26 '12 at 18:28
But in this case what about odd length?I.e. aaa becomes #a#a#a#.So now center is second a. Not a #? –  Cratylus May 26 '12 at 18:39

Your Answer


