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.
相关问题
- Finding k smallest elements in a min heap - worst-
- binary search tree path list
- High cost encryption but less cost decryption
- How to get a fixed number of evenly spaced points
- Space complexity of validation of a binary search
相关文章
- What are the problems associated to Best First Sea
- Coin change DP solution to keep track of coins
- Algorithm for partially filling a polygonal mesh
- Robust polygon normal calculation
- Algorithm for maximizing coverage of rectangular a
- How to measure complexity of a string?
- Select unique/deduplication in SSE/AVX
- How to smooth the blocks of a 3D voxel world?
The Linear solution can be found in this Way ::
Prequisities:
(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.
Step 2: Now construct the Suffix Array of the string Str.
In this example ,the suffix array is:
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.
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.
Execution Example ::
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 # ".
A few years late...
Assume
s
is the original string, andr
iss
reversed. Let's also assume we've completely built a suffix treeST
usings
.Our next step is to check all the suffixes of
r
againstST
. With each new suffix ofr
, we'll maintain a count of the firstk
characters we've matched successfully against a preexisting suffix in the tree (ie, one ofs
's suffixes).As an example, say we're matching the suffix "RAT" from
r
, ands
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 ofr
's suffix with the first two characters ofs
's suffix. We'll call this node that we reachedn
.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 ofn
.Let's use these indices.
What does it mean if we match
k
characters of one ofR
's substrings againstk
characters inST
? Well, it simply means we found some string reversed. But what does it mean if the location where the substring begins inR
is equal to the matched substring inS
plusk
? Yes, it meanss[i] through s[i+k]
reads the same ass[i+k] through s[i]
! And so, be definition we've located a palindrome of sizek
.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.
DP solution:
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.
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.
EXAMPLE
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:
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
EDIT
I've just found this paper that answers this question.