Difference between revisions of "Longest palindromic subsequence"

From PEGWiki
Jump to: navigation, search
(→‎Shortest palindromic supersequence)
Line 1: Line 1:
 +
{{Distinguish|Longest palindromic substring}}
 +
 
The '''longest palindromic subsequence''' problem is the problem of finding the longest subsequence of a string (a subsequence is obtained by deleting some of the characters from a string without reordering the remaining characters) which is also a palindrome. In general, the longest palindromic subsequence is not unique. For example, the string '''alfalfa''' has two palindromic subsequences of length 5: '''alala''' and '''afafa'''. However, it does not have any palindromic subsequences longer than five characters. Therefore '''alala''' and '''afafa''' are both considred longest palindromic subsequences of '''alfalfa'''.
 
The '''longest palindromic subsequence''' problem is the problem of finding the longest subsequence of a string (a subsequence is obtained by deleting some of the characters from a string without reordering the remaining characters) which is also a palindrome. In general, the longest palindromic subsequence is not unique. For example, the string '''alfalfa''' has two palindromic subsequences of length 5: '''alala''' and '''afafa'''. However, it does not have any palindromic subsequences longer than five characters. Therefore '''alala''' and '''afafa''' are both considred longest palindromic subsequences of '''alfalfa'''.
  

Revision as of 23:23, 14 November 2010

Not to be confused with Longest palindromic substring.

The longest palindromic subsequence problem is the problem of finding the longest subsequence of a string (a subsequence is obtained by deleting some of the characters from a string without reordering the remaining characters) which is also a palindrome. In general, the longest palindromic subsequence is not unique. For example, the string alfalfa has two palindromic subsequences of length 5: alala and afafa. However, it does not have any palindromic subsequences longer than five characters. Therefore alala and afafa are both considred longest palindromic subsequences of alfalfa.

Precise statement

Three variations of this problem may be distinguished:

  • Find the maximum possible length for a palindromic subsequence.
  • Find some palindromic subsequence of maximal length.
  • Find all longest palindromic subsequences.

Theorem: Returning all longest palindromic subsequences cannot be accomplished in worst-case polynomial time.

Proof: Consider a string made up of N/2 ones, followed by N/4 zeroes, and finally N/4 ones. (Assume N is a multiple of 4, although it does not really matter.) Any palindromic substring either does not contain any zeroes, in which case its length is only up to 3N/4, or it contains at least one zero. If it contains at least one zero, it must be of the form 1^a0^b1^c, but a and c must be equal. (This is because the middle of the palindrome must lie somewhere within the zeroes, otherwise there would be no zeroes on one side of it and at least one zero on the other side; but as long as the middle lies within the zeroes, there must be an equal number of ones on each side.) But c can only be up to N/4, and likewise with b, so again the palindrome cannot be longer than 3N/4 characters. However, there are \binom{N/2}{N/4}+1 palindromic substrings of length 3N/4; we can either take all the ones, or we can take all N/4 zeroes, all N/4 terminal ones, and N/4 out of the N/2 initial ones. Thus the output size is not polynomial in N, and then neither can the algorithm be in the worst case. _\blacksquare

However, this does not rule out the existence of a polynomial-time algorithm for the first two variations on the problem. We now present such an algorithm.

Theoretical background

(Note: these Lemmas are "obvious" and their proofs will probably not help you intuitively understand how the algorithm works, so skip them if they are too heavy in mathematical notation for you.)

Lemma 1: Any palindromic subsequence s of a string S is a common subsequence of S and its reverse S'.

Proof: Since s is a subsequence of S, its reverse s' is a subsequence of S' But s = s' since s is a palindrome, so s is a subsequence of S', and hence a common subsequence. _\blacksquare

Lemma 2: If there exists a common subsequence s of length L of S and its reverse S', then there exists a palindromic subsequence s^* of S of length greater than or equal to L which is a supersequence of s.

Proof: Let s denote the subsequence in S and s' denote the subsequence in S'. Let {s^*}' denote a supersequence of s'. Walk through the string S from left to right. that is, consider S_i as i goes from 0 to N-1. Let i' denote N-i-1, so that S_i = S'_{i'} at all times. For each value of i:

  • If S_i is in s then S_i is in s^* and S'_{i'} is in {s^*}'.
  • If S_i is not in s but S'_{i'} is in s', then, again, S_i is in s^* and S'_{i'} is in {s^*}'.
  • Otherwise, S_i is not in s^* and S'_{i'} is not in {s^*}'.

After this has completed, s^* is clearly a supersequence of s and a subsequence of S, and likewise {s^*}' is a supersequence of s' and a subsequence of S'.

Furthermore, s^* and {s^*}' are reverses of each other, because whenever a character S_i is added to the end of s^*, the identical character S'_{i'} is added to the beginning of {s^*}', and vice versa.

Now consider the ith character in s^*. This is S_j where j is the ith smallest index for which either S_j is in s or S'_{j'} is in s'. This means that j' is the ith largest index for which either S'_{j'} is in s' or S_j is in s, since S and S' are reverses of each other. Therefore, S'_{j'} is the ith character in {s*}' (characters near the beginning of {s*}' originate from near the beginning of S' or the end of S). But the ith character in {s*}' is the (n-i-1)st character in s*, because s* and {s*}' are reverses of each other. Therefore s* is palindromic. _\blacksquare

Theorem: Any longest common subsequence s of S and its reverse S' is a longest palindromic subsequence of S.

Proof: Suppose s is not palindromic. By Lemma 2, we know we can obtain a palindrome s* that is a supersequence of s and a subsequence of S. This cannot be s itself since s is not palindromic. So s* must be longer than s. By Lemma 1, s* is a common subsequence of S and S'. However, as s* is longer than s, this contradicts s having been a longest common subsequence of S and S'.

Likewise, suppose s is a longest common subsequence of S and S' and palindromic but it is not a longest palindromic subsequence of S. Then there again exists a longer palindromic subsequence of S, which gives a longer common subsequence of S and S', a contradiction. _\blacksquare

Algorithm

A corollary of the Theorem is that a longest palindromic subsequence of S can be found in O(|S|^2) time simply by finding the longest common subsequence of S and its reverse.

Note that there exist more efficient algorithms for finding longest common subsequences, which also give more efficient means of computing longest palindromic subsequences.

Shortest palindromic supersequence

It can also be shown that the shortest palindromic supersequence of a string S can be found by taking the shortest common supersequence of S and its reverse. The proof is left as an exercise to the reader.

External links

Retrieved from "http://wcipeg.com/wiki/index.php?title=Longest_palindromic_subsequence&oldid=506"