Longest palindromic subsequence - Revision history

162.158.62.29: removing confusing statement from proof

2022-05-03T01:10:05Z

removing confusing statement from proof

108.162.219.202: Typo

2020-01-07T07:10:42Z

Typo

Spundun: /* LCS-based approach */ six, not three LPSes

2014-09-27T03:31:53Z

‎LCS-based approach: six, not three LPSes

Spundun: /* LCS-based approach */ again four LPSes

2014-09-27T01:42:19Z

‎LCS-based approach: again four LPSes

Spundun: There are atleast 4 palidromic subsequences of length 5

2014-09-27T01:33:08Z

There are atleast 4 palidromic subsequences of length 5

123.201.60.154: /* Direct solution */

2013-11-24T08:13:58Z

‎Direct solution

Brian at 23:39, 10 June 2012

2012-06-10T23:39:36Z

Brian: anonymous comment was right: all the math in this article was wrong

2012-05-27T02:02:39Z

anonymous comment was right: all the math in this article was wrong

80.167.121.74: /* Theoretical background */

2012-05-23T00:07:55Z

‎Theoretical background

Brian at 20:07, 3 April 2011

2011-04-03T20:07:05Z

@@ Line 11: / Line 11: @@
 '''Theorem''': Returning all longest palindromic subsequences cannot be accomplished in worst-case polynomial time.
-'''Proof'''<ref name="schneider">Jonathan T. Schneider (2010). Personal communication.</ref>: Consider a string made up of <math>N/2</math> ones, followed by <math>N/4</math> zeroes, and finally <math>N/4</math> ones. (Assume <math>N</math> is a multiple of 4, although it does not really matter.) Any palindromic subsequence either does not contain any zeroes, in which case its length is only up to <math>3N/4</math>, or it contains at least one zero. If it contains at least one zero, it must be of the form <math>1^a0^b1^c</math>, but <math>a</math> and <math>c</math> 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 <math>c</math> can only be up to <math>N/4</math>, and likewise with <math>b</math>, so again the palindrome cannot be longer than <math>3N/4</math> characters. However, there are <math>\binom{N/2}{N/4}+1</math> palindromic subsequences of length <math>3N/4</math>; we can either take all the ones, or we can take all <math>N/4</math> zeroes, all <math>N/4</math> terminal ones, and <math>N/4</math> out of the <math>N/2</math> initial ones. Thus the output size is not polynomial in <math>N</math>, and then neither can the algorithm be in the worst case. <math>_\blacksquare</math>
+'''Proof'''<ref name="schneider">Jonathan T. Schneider (2010). Personal communication.</ref>: Consider a string made up of <math>N/2</math> ones, followed by <math>N/4</math> zeroes, and finally <math>N/4</math> ones. Any palindromic subsequence either does not contain any zeroes, in which case its length is only up to <math>3N/4</math>, or it contains at least one zero. If it contains at least one zero, it must be of the form <math>1^a0^b1^c</math>, but <math>a</math> and <math>c</math> 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 <math>c</math> can only be up to <math>N/4</math>, and likewise with <math>b</math>, so again the palindrome cannot be longer than <math>3N/4</math> characters. However, there are <math>\binom{N/2}{N/4}+1</math> palindromic subsequences of length <math>3N/4</math>; we can either take all the ones, or we can take all <math>N/4</math> zeroes, all <math>N/4</math> terminal ones, and <math>N/4</math> out of the <math>N/2</math> initial ones. Thus the output size is not polynomial in <math>N</math>, and then neither can the algorithm be in the worst case. <math>_\blacksquare</math>
 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.

@@ Line 1: / Line 1: @@
 {{Distinguish|Longest palindromic substring}}
-The '''longest palindromic subsequence''' (LPS) 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 four palindromic subsequences of length 5: '''alala''', '''afafa''', '''alfla''', and '''aflfa'''. However, it does not have any palindromic subsequences longer than five characters. Therefore all four are considred longest palindromic subsequences of '''alfalfa'''.
+The '''longest palindromic subsequence''' (LPS) 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 four palindromic subsequences of length 5: '''alala''', '''afafa''', '''alfla''', and '''aflfa'''. However, it does not have any palindromic subsequences longer than five characters. Therefore all four are considered longest palindromic subsequences of '''alfalfa'''.
 ==Precise statement==

@@ Line 19: / Line 19: @@
 The standard algorithm for computing a longest palindromic subsequence of a given string <var>S</var> involves first computing a [[longest common subsequence]] (LCS) of <var>S</var> and its reverse <var>S'</var>. Often, this gives a correct LPS right away. For example, the reader may verify that '''alala''', '''afafa''', '''aflfa''' and '''alfla''' are all LCSes of '''alfalfa''' and its reverse '''aflafla'''. However, this is not ''always'' the case; for example, '''afala''' and '''alafa''' are ''also'' LCSes of '''alfalfa''' and its reverse, yet neither is palindromic. While it is clear that any LPS of a string is an LCS of the string and its reverse, the converse is false.
-However, with a slight modification, this algorithm can be made to work. We will use the example string '''ABCDEBCA''', which has three LPSes: '''ABCBA''', '''ABDBA''', and '''ACDCA''' (and our objective is to find one of them). Suppose that we find an LCS which is not one of these, such as <var>L</var>&nbsp;=&nbsp;'''ABDCA''':
+However, with a slight modification, this algorithm can be made to work. We will use the example string '''ABCDEBCA''', which has six LPSes: '''ABCBA''', '''ABDBA''', '''ABEBA''', '''ACDCA''', '''ACECA''' and '''ACBCA''' (and our objective is to find one of them). Suppose that we find an LCS which is not one of these, such as <var>L</var>&nbsp;=&nbsp;'''ABDCA''':
 : '''AB'''C'''D'''EB'''CA'''
 : '''A'''C'''B'''E'''DC'''B'''A'''

@@ Line 17: / Line 17: @@
 ==Algorithm==
 ===LCS-based approach===
-The standard algorithm for computing a longest palindromic subsequence of a given string <var>S</var> involves first computing a [[longest common subsequence]] (LCS) of <var>S</var> and its reverse <var>S'</var>. Often, this gives a correct LPS right away. For example, the reader may verify that '''alala''' and '''afafa''' are both LCSes of '''alfalfa''' and its reverse '''aflafla'''. However, this is not ''always'' the case; for example, '''afala''' and '''alafa''' are ''also'' LCSes of '''alfalfa''' and its reverse, yet neither is palindromic. While it is clear that any LPS of a string is an LCS of the string and its reverse, the converse is false.
+The standard algorithm for computing a longest palindromic subsequence of a given string <var>S</var> involves first computing a [[longest common subsequence]] (LCS) of <var>S</var> and its reverse <var>S'</var>. Often, this gives a correct LPS right away. For example, the reader may verify that '''alala''', '''afafa''', '''aflfa''' and '''alfla''' are all LCSes of '''alfalfa''' and its reverse '''aflafla'''. However, this is not ''always'' the case; for example, '''afala''' and '''alafa''' are ''also'' LCSes of '''alfalfa''' and its reverse, yet neither is palindromic. While it is clear that any LPS of a string is an LCS of the string and its reverse, the converse is false.
 However, with a slight modification, this algorithm can be made to work. We will use the example string '''ABCDEBCA''', which has three LPSes: '''ABCBA''', '''ABDBA''', and '''ACDCA''' (and our objective is to find one of them). Suppose that we find an LCS which is not one of these, such as <var>L</var>&nbsp;=&nbsp;'''ABDCA''':

@@ Line 1: / Line 1: @@
 {{Distinguish|Longest palindromic substring}}
-The '''longest palindromic subsequence''' (LPS) 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''' (LPS) 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 four palindromic subsequences of length 5: '''alala''', '''afafa''', '''alfla''', and '''aflfa'''. However, it does not have any palindromic subsequences longer than five characters. Therefore all four are considred longest palindromic subsequences of '''alfalfa'''.
 ==Precise statement==

@@ Line 41: / Line 41: @@
 + f(i+1,j-1) & \text{if } j-i > 1 \text{ and } S_i = S_{j-1}
 \end{cases}</math>
 ==References==

@@ Line 14: / Line 14: @@
 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.
 ==Algorithm==
-A corollary of the Theorem is that a longest palindromic subsequence of <math>S</math> can be found in <math>O(|S|^2)</math> time simply by finding the longest common subsequence of <math>S</math> and its reverse.
+todo
-−
-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 <math>S</math> can be found by taking the [[Longest_common_subsequence#Shortest_common_supersequence|shortest common supersequence]] of <math>S</math> and its reverse. The proof is left as an exercise to the reader.
 ==References==

← Older revision		Revision as of 00:07, 23 May 2012
Line 23:		Line 23:

	''Lemma 2'': If there exists a common subsequence <math>s</math> of length <math>L</math> of <math>S</math> and its reverse <math>S'</math>, then there exists a palindromic subsequence <math>s^*</math> of <math>S</math> of length greater than or equal to <math>L</math> which is a supersequence of <math>s</math>.		''Lemma 2'': If there exists a common subsequence <math>s</math> of length <math>L</math> of <math>S</math> and its reverse <math>S'</math>, then there exists a palindromic subsequence <math>s^*</math> of <math>S</math> of length greater than or equal to <math>L</math> which is a supersequence of <math>s</math>.
		+
		+	''This lemma is false'': Consider the sequence "abacbab" and its reverse, which has 6 (longest) common subsequences of length 5; "ababa", "babab", "bacab", "abcba", "abcab" and "bacba". The last two are obviously not palindromic, and there does not exist palindromic supersequences that are also subsequences of "abacbab".

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