how to find longest palindromic subsequence?
|
7:55 PM |
No comments |
how to find longest palindromic subsequence?
Here is the problem (6.7 ch6 ) from Algorithms book (by Vazirani) that slightly differs from the classical problem that finding longest palindrome. How can I solve this problem ?
A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence
A,C,G,T,G,T,C,A,A,A,A,T,C,Ghas many palindromic subsequences, including
A,C,G,C,AandA,A,A,A(on the other hand, the subsequenceA,C,Tis not palindromic). Devise an algorithm that takes a sequencex[1 ...n]and returns the (length of the) longest palindromic subsequence. Its running time should beO(n^2)
Answer by SivGo for how to find longest palindromic subsequence?
for each letter in the string:
set the letter as the middle of the palindrome (current Length = 1)
check how long would be the palindrome if this is its middle
if this palindrome is longer than the one we found (until now) : keep the index and the size of the palindrome.
O(N^2) : since we have one loop that choose the middle and one loop that check how long the palindrome if this is the middle. each loop runs from 0 to O(N) [the first one from 0 to N-1 and the second one is from 0 to (N-1)/2]
for example: D B A B C B A
i=0 : D is the middle of the palindrome, can't be longer than 1 (since it's the first one)
i=1: B is the middle of the palindrome, check char before and after B : not identical (D in one side and A in the other) --> length is 1.
i=2 : A is middle of the palindrome, check char before and after A : both B --> length is 3. check chars with gap of 2: not identiacl (D in one side and C in the other) --> length is 3.
etc.
Answer by MAK for how to find longest palindromic subsequence?
This can be solved in O(n^2) using dynamic programming. Basically, the problem is about building the longest palindromic subsequence in x[i...j] using the longest subsequence for x[i+1...j], x[i,...j-1] and x[i+1,...,j-1] (if first and last letters are the same).
Firstly, the empty string and a single character string is trivially a palindrome. Notice that for a substring x[i,...,j], if x[i]==x[j], we can say that the length of the longest palindrome is the longest palindrome over x[i+1,...,j-1]+2. If they don't match, the longest palindrome is the maximum of that of x[i+1,...,j] and y[i,...,j-1].
This gives us the function:
longest(i,j)= j-i+1 if j-i<=0, 2+longest(i+1,j-1) if x[i]==x[j] max(longest(i+1,j),longest(i,j-1)) otherwise You can simply implement a memoized version of that function, or code a table of longest[i][j] bottom up.
This gives you only the length of the longest subsequence, not the actual subsequence itself. But it can easily be extended to do that as well.
Answer by Peter Lawrey for how to find longest palindromic subsequence?
This can be solved in O(n) very simply. A palindrome can have any number of letters which appear an even number of times, but at most one letter which appears an odd number of times.
If you can choose which letters to use, add all the letters (to the start and end) which appear an even number of times and add a letter which occurs an odd number of times to the center.
You can do this with two passes, first to count the number of occurences, the second to build the string.
Answer by lone_wolf for how to find longest palindromic subsequence?
Input : A1,A2,....,An
Goal : Find the longest strictly increasing subsequence (not necessarily contiguous)?.
L(j): Longest strictly increasing subsequence ending at j
L(j): max{ L(i)}+1 } where i < j and A[i] < A[j]
Then find max{ L(j) } for all j
You will get the source code here
Answer by user2159588 for how to find longest palindromic subsequence?
Working Java Implementation of Longest Palindrome Sequence
public class LongestPalindrome { int max(int x , int y) { return (x>y)? x:y; } int lps(char[] a ,int i , int j) { if(i==j) //If only 1 letter { return 1; } if(a[i] == a[j] && (i+1) == j) // if there are 2 character and both are equal { return 2; } if(a[i] == a[j]) // If first and last char are equal { return lps(a , i+1 , j-1) +2; } return max(lps(a,i+1 ,j),lps(a,i,j-1)); } public static void main(String[] args) { String s = "NAMAN IS NAMAN"; LongestPalindrome p = new LongestPalindrome(); char[] c = s.toCharArray(); System.out.print("Length of longest seq is" + p.lps(c,0,c.length-1)); } } Answer by rararabbit for how to find longest palindromic subsequence?
It makes me a little confused that the difference between substring and subsequence.(See Ex6.8 and 6.11) According to our comprehension of subsequence, the giving example doesn't have the palindromic subsequence ACGCA. Here's my pseudo code, I'm not quite sure about the initialization ><
for i = 1 to n do for j = 1 to i-1 do L(i,j) = 0 for i = 1 to n do L(i,i) = 1 for i = n-1 to 1 do //pay attention to the order when filling the table for j = i+1 to n do if x[i] = x[j] then L(i,j) = 2 + L(i+1, j-1) else do L(i,j) = max{L(i+1, j), L(i, j-1)} return max L(i,j) preparing for the algorithm final...
Answer by ankitG for how to find longest palindromic subsequence?
This problem can also be done as a variation of a very common problem called the LCS(Longest Common sub sequence) problem. Let the input string be represented by a character array s1[0...n-1].
1) Reverse the given sequence and store the reverse in another array say s2[0..n-1] which in essence is s1[n-1....0]
2) LCS of the given sequence s1 and reverse sequence s2 will be the longest palindromic sequence.
This solution is also a O(n^2) solution.
Answer by Mohit Motiani for how to find longest palindromic subsequence?
import java.util.HashSet;
import java.util.Scanner;
/** * @param args * We are given a string and we need to find the longest subsequence in that string which is palindrome * In this code we have used hashset in order to determine the unique set of substring in the given strings */
public class NumberOfPalindrome {
/** * @param args * Given a string find the longest possible substring which is a palindrome. */ public static HashSet h = new HashSet<>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); for(int i=0;i<=s.length()/2;i++) h.add(s.charAt(i)+""); longestPalindrome(s.substring(0, (s.length()/2)+(s.length()%2))); System.out.println(h.size()+s.length()/2); System.out.print(h); } public static void longestPalindrome(String s){ //System.out.println(s); if(s.length()==0 || s.length()==1) return; if(checkPalindrome(s)){ h.add(s); } longestPalindrome(s.substring(0, s.length()-1)); longestPalindrome(s.substring(1, s.length())); } public static boolean checkPalindrome(String s){ //System.out.println(s); int i=0;int j=s.length()-1; while(i<=j){ if(s.charAt(i)!=s.charAt(j)) return false; i++;j--; } return true; } } Answer by John for how to find longest palindromic subsequence?
private static int findLongestPalindromicSubsequence(String string) { int stringLength = string.length(); int[][] l = new int[stringLength][stringLength]; for(int length = 1; length<= stringLength; length++){ for(int left = 0;left<= stringLength - length;left++){ int right = left+ length -1; if(length == 1){ l[left][right] = 1; } else{ if(string.charAt(left) == string.charAt(right)){ //L(0, n-1) = L(1, n-2) + 2 if(length == 2){ // aa l[left][right] = 2; } else{ l[left][right] = l[left+1][right-1]+2; } } else{ //L(0, n-1) = MAX ( L(1, n-1) , L(0, n-2) ) l[left][right] = (l[left+1][right] > l[left][right-1])?l[left+1][right] : l[left][right-1]; } } } } return l[0][stringLength-1]; } Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72
0 comments:
Post a Comment