Question

5

Dynamic Programming. A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length 1, civic, racecar, and aibohphobia (fear of palindromes). Give an efficient algorithm to find the longest palindrome that is a sunsequence of a given input string. For example, given the input character, your algorithm should return carac. What is the running time of your algorithm?

Answer 1

I believe you need to proceed this way:

Let y₁y₂ ... y_n be your string (where y_i are letters).

Create the generalized suffix tree of S_f = y₁y₂ ... y_n$ and S_r = y_ny_{n - 1} ... y₁# (reverse the letters and choose different ending characters for S_f ($) and S_r (#))... where S_f stands for "String, Forward" and S_r stands for "String, Reverse".

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

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.

S_f = banana$

S_r = ananab#

Below is the generalised suffix tree of S_f and S_r, 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:

B# 4 AB# NA AI ANANAS 4 B# 0 NA AB# B# 0

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