Take the 2-minute tour ×

I was trying to find the longest palindrome in a string. The brute force solution takes O(n^3) time. I read that there is a linear time algorithm for it using suffix trees. I am familiar with suffix trees and am comfortable building them. How do you use the built suffix tree to find the longest palindrome.

share|improve this question
Brute force only takes O(N^2) time. –  tskuzzy Aug 12 '11 at 17:32
It is not a duplicate of the above link. Try to understand the question. The answers in the above question give a super linear algorithm at best without suffix tree. I am looking at an O(n) solution using suffix trees. –  shreyasva Aug 12 '11 at 17:43
So then your question is more like "Suppose I built a suffix tree - how could I use this tree to find palindromes?" It seems related, but not a duplicate of the linked question. –  corsiKa Aug 12 '11 at 18:02
I cannot vote to reopen, but it's not a duplicate!!! It's a specific interview question, the interewer first expects suffix trees (nothing to do with the other answer) and an intuitive explaination on how it works. Not 100 lines of code nor a whole theory on how to find palindrome in a genetic sequence of 10 billion ACGT as fast as possible (johanjeuring.blogspot.com/2007/08/finding-palindromes.html) ... –  Ricky Bobby Aug 12 '11 at 22:12
Re-opened after viewing the conversation in comments. –  Tim Post Aug 13 '11 at 18:59

5 Answers 5

up vote 25 down vote accepted

I believe you need to proceed this way:

Let y1y2 ... yn be your string (where yi are letters).

Create the generalized suffix tree of Sf = y1y2 ... yn$ and Sr = ynyn - 1 ... y1# (reverse the letters and choose different ending characters for Sf ($) and Sr (#))... where Sf stands for "String, Forward" and Sr stands for "String, Reverse".

For every suffix i in Sf, find the lowest common ancestor with the suffix n - i + 1 in Sr.

What runs from the root till this lowest common ancestor is a palindrome, because now the lowest common ancestor represents the longest common prefix of these two suffixes. Recall that:

(1) A prefix of a suffix is a substring.

(2) A palindrome is a string identical to its reverse.

(3) So the longest contained palindrome within a string is exactly the longest common substring of this string and its reverse.

(4) Thus, the longest contained palindrome within a string is exactly the longest common prefix of all pairs of suffixes between a string and its reverse. This is what we're doing here.


Let's take the word banana.

Sf = banana$

Sr = ananab#

Below is the generalised suffix tree of Sf and Sr, where the number at the end of each path is the index of the corresponding suffix. There's a small mistake, the a common to all the 3 branches of Blue_4's parent should be on its entering edge, beside n:

enter image description here

The lowest interior node in the tree is the longest common substring of this string and its reverse. Looking at all the interior nodes in the tree you will therefore find the longest palindrome.

The longest palindrome is found between between Green_0 and Blue_1 (i.e., banana and anana) and is anana


I've just found this paper that answers this question.

share|improve this answer
@ricky-boby : Are you sure about your 3rd and 4th claim? For example, the string: xyztuvananakvutzyx and its reverse xyztuvkananavutzyx have xyztuv as their longest common prefix but xyztuv is not a plaindrome. –  CEGRD Dec 16 '12 at 6:25
@CEGRD is correct, this answer wasted my time. –  agou May 3 '13 at 4:21
This answer is wrong as CEGRD pointed out.. –  user1715122 Nov 19 '13 at 5:00
wrong answer.... –  Nitin Garg Dec 29 '13 at 9:06
Please fix this answer. I think you just need to check whether the length of the palindrome plus the starting index in the forward string and the starting index in the reverse string equals the length of the original string. –  Neil G Jan 15 '14 at 21:04

The Linear solution can be found in this Way ::


(1).You must know how to construct the suffix array in O(N) or O(NlogN) time.

(2).You must know how to find the standard LCP Array ie. LCP between adjacent Suffixes i and i-1

ie . LCP [i]=LCP(suffix i in sorted array, suffix i-1 in sorted array) for (i>0).

Let S be the Original String and S' be the reverse of Original String. Lets take S="banana" as an example. Then its Reverse string S'=ananab.

Step 1: Concatenate S + # + S' to get String Str ,where # is an alphabet not present in original String.

    Concatenated String Str=S+#+S'

Step 2: Now construct the Suffix Array of the string Str.

In this example ,the suffix array is:

Suffix Number   Index   Sorted Suffix
0               6       #ananab
1               5       a#ananab
2               11      ab
3               3       ana#ananab
4               9       anab
5               1       anana#ananab
6               7       ananab
7               12      b
8               0       banana#ananab
9               4       na#ananab
10              10      nab
11              2       nana#ananab
12              8       nanab

Please Note that a suffix array is an array of integers giving the starting positions of suffixes of a string in lexicographical order.So the Array that holds Index of starting position is a suffix Array.

That is SuffixArray[]={6,5,11,3,9,1,7,12,0,4,10,2,8};

Step 3: As you had managed to construct the Suffix Array ,Now find the Longest Common Prefixes Between the adjacent suffixes.

LCP between #ananab        a#ananab          is :=0
LCP between a#ananab       ab                is :=1
LCP between ab             ana#ananab        is :=1
LCP between ana#ananab     anab              is :=3
LCP between anab           anana#ananab      is :=3
LCP between anana#ananab   ananab            is :=5
LCP between ananab         b                 is :=0
LCP between b              banana#ananab     is :=1
LCP between banana#ananab  na#ananab         is :=0
LCP between na#ananab      nab               is :=2
LCP between nab            nana#ananab       is :=2
LCP between nana#ananab nanab                is :=4

Thus LCP array LCP={0,0,1,1,3,3,5,0,1,0,2,2,4}.

Where LCP[i]=Length of Longest Common Prefix between Suffix i and suffix (i-1). (for i>0)

Step 4:

Now you have constructed a LCP array ,Use the following Logic.

    Let the length of the Longest Palindrome ,longestlength:=0 (Initially)
    Let Position:=0.
    for(int i=1;i<Len;++i)
        //Note that Len=Length of Original String +"#"+ Reverse String
            //Note Actual Len=Length of original Input string .
            if((suffixArray[i-1]<actuallen && suffixArray[i]>actuallen)||(suffixArray[i]<actuallen && suffixArray[i-1]>actuallen))
                 //print :Calculating Longest Prefixes b/w suffixArray[i-1] AND  suffixArray[i]

              //print The Longest Prefix b/w them  is ..
              //print The Length is :longestlength:=LCP[i];
    So the length of Longest Palindrome :=longestlength;
    and the longest palindrome is:=Str[position,position+longestlength-1];

Execution Example ::

    actuallen=Length of banana:=6
    Len=Length of "banana#ananab" :=13.

Calculating Longest Prefixes b/w a#ananab AND  ab
The Longest Prefix b/w them  is :a 
The Length is :longestlength:= 1 
Position:= 11

Calculating Longest Prefixes b/w ana#ananab AND  anab
The Longest Prefix b/w them  is :ana
The Length is :longestlength:= 3 

Calculating Longest Prefixes b/w anana#ananab AND  ananab
The Longest Prefix b/w them  is :anana
The Length is :longestlength:= 5 
Position:= 7

So Answer =5.
And the Longest Palindrome is :=Str[7,7+5-1]=anana

Just Make a Note ::

The if condition in Step 4 basically refers that ,in each iteration(i) ,if I take the suffixes s1(i) and s2(i-1) then ,"s1 must contains # and s2 must not contain # " OR "s2 must contains # and s1 must not contains # ".

     |     |      |      |(7:#ANANAB)|leaf
     |     |      |(5:NA)|
     |     |      |      |(13:B)|leaf
     |     |(3:NA)|
     |     |      |(7:#ANANAB)|leaf
     |     |      |
     |     |      |(13:B)|leaf
     |     |(7:#ANANAB)|leaf
     |     |
     |     |(13:B)|leaf
     |      |      |(7:#ANANAB)|leaf
     |      |(5:NA)|
     |      |      |(13:B)|leaf
     |      |(7:#ANANAB)|leaf
     |      |
     |      |(13:B)|leaf
share|improve this answer
I must say Amazing Explanation.. Thanks it help me to solve the Spoj problem LPS –  user1134599 Jul 10 '12 at 17:40
And yeah +1 for perfect illustrations :) –  user1134599 Jul 10 '12 at 17:40
thanks for the explanation, although for this case: 1234xaba4321, will this algorithm select 1234 or 4321 instead of aba as the result? –  poiu2000 Mar 28 '13 at 3:41
Excellently done using beautiful illustration and example :) –  Dipesh Gupta Mar 9 '14 at 21:40
as pointed out by poiu2000, this alggorithm is not correct –  jason zhang Nov 2 '14 at 4:50

Simple and short explanation from Skiena - The Algorithm Design Manual

Find the longest palindrome in S [using suffix tree] – A palindrome is a string that reads the same if the order of characters is reversed, such as madam. To find the longest palindrome in a string S, build a single suffix tree containing all suffixes of S and the reversal of S, with each leaf identified by its starting position. A palindrome is defined by any node in this tree that has forward and reversed children from the same position.

share|improve this answer

A few years late...

Assume s is the original string, and r is s reversed. Let's also assume we've completely built a suffix tree ST using s.

Our next step is to check all the suffixes of r against ST. With each new suffix of r, we'll maintain a count of the first k characters we've matched successfully against a preexisting suffix in the tree (ie, one of s's suffixes).

As an example, say we're matching the suffix "RAT" from r, and s contained some suffixes beginning with "RA", but none that matched "RAT". k would equal 2 when we finally had to abandon hope for the final characters "T". We matched the first two characters of r's suffix with the first two characters of s's suffix. We'll call this node that we reached n.

Now, how do we know when we've found a palindrome? By checking all leaf nodes under n.

In a traditional suffix tree, the starting index of each suffix is stored at the leaf node of that suffix branch. In our above example, s may have contained a bunch of suffixes starting with "RA", each of which begins at one of the indexes present in the leaf node descendants of n.

Let's use these indices.

What does it mean if we match k characters of one of R's substrings against k characters in ST? Well, it simply means we found some string reversed. But what does it mean if the location where the substring begins in R is equal to the matched substring in S plus k? Yes, it means s[i] through s[i+k] reads the same as s[i+k] through s[i]! And so, be definition we've located a palindrome of size k.

Now, all you have to do is keep a tab on the longest palindrome found so far, and return it at the end of your function.

share|improve this answer
Can you elaborate on why the previous answers are wrong? –  templatetypedef Jan 8 at 3:47
@templatetypedef Have a look at the comments below each one. They contain counterexamples. I'm referring to the two with solutions with the most votes. –  sgarza62 Jan 8 at 3:49

DP solution:

int longestPalin(char *str)
    n = strlen(str);
    bool table[n][n]l
    memset(table, 0, sizeof(table));
    int start = 0;

        table[i][i] = true;
    int maxlen = 1;

    for(int i=0; i<n-1; ++i)
        if(str[i] == str[i+1])
            table[i][i] = true;
            start = i;
            maxlen = 2;

    for(int k=3; k<=n; ++k)
        for(int i=0; i<n-k+1; ++i)
            int j = n+k-1;
            if(str[i] == str[j] && table[i+1][j-1])
                table[i][j] = true;
                if(k > maxlen)
                    start = i;
                    maxlen = k;
    print(str, start, start+maxlen-1);
    return maxlen;
share|improve this answer
The question was "using suffix tree" not with DP. –  Zsolt Safrany Nov 1 '14 at 11:51

Your Answer


