¿cómo encontrar la subsecuencia palindrómica más larga?

Aquí está el problema (6.7 ch6 ) del libro de Algoritmos (por Vazirani) que difiere ligeramente del problema clásico de encontrar el palíndromo más largo . Como puedó resolver esté problema ?

Una subsecuencia es palindrómica si es la misma si se lee de izquierda a derecha o de derecha a izquierda. Por ejemplo, la secuencia

A,C,G,T,G,T,C,A,A,A,A,T,C,G 

tiene muchas subsecuencias palindrómicas, que incluyen A,C,G,C,A y A,A,A,A (por otro lado, la subsecuencia A,C,T no es palindrómica). Diseñe un algoritmo que tome una secuencia x[1 ...n] y devuelva la (longitud de) la subsecuencia palindrómica más larga. Su tiempo de ejecución debe ser O(n^2)

Esto se puede resolver en O (n ^ 2) usando progtwigción dinámica. Básicamente, el problema es construir la subsecuencia palindrómica más larga en x[i...j] usando la subsecuencia más larga para x[i+1...j] , x[i,...j-1] y x[i+1,...,j-1] (si la primera y la última letra son las mismas).

En primer lugar, la cadena vacía y la cadena de un solo carácter es trivialmente un palíndromo. Observe que para una subcadena x[i,...,j] , si x[i]==x[j] , podemos decir que la longitud del palíndromo más largo es el palíndromo más largo sobre x[i+1,...,j-1]+2 . Si no coinciden, el palíndromo más largo es el máximo de x[i+1,...,j] y y[i,...,j-1] .

Esto nos da la función:

 longest(i,j)= j-i+1 if ji<=0, 2+longest(i+1,j-1) if x[i]==x[j] max(longest(i+1,j),longest(i,j-1)) otherwise 

Simplemente puede implementar una versión memorada de esa función, o codificar una tabla de mayor [i] [j] de abajo hacia arriba.

Esto le da solo la longitud de la subsecuencia más larga, no la subsecuencia propiamente dicha. Pero puede extenderse fácilmente para hacer eso también.


Este problema también se puede hacer como una variación de un problema muy común llamado el problema LCS (sub secuencia común más larga). Deje que la cadena de entrada se represente mediante una matriz de caracteres s1 [0 … n-1].

1) Invierta la secuencia dada y almacene el reverso en otra matriz diga s2 [0..n-1] que en esencia es s1 [n-1 …. 0]

2) LCS de la secuencia dada s1 y secuencia inversa s2 será la secuencia palindrómica más larga.

Esta solución también es una solución O (n ^ 2).

Me hace un poco confuso que la diferencia entre subcadena y subsecuencia. (Ver Ex6.8 y 6.11) Según nuestra comprensión de la subsecuencia, el ejemplo que da no tiene la subsecuencia palindrómica ACGCA. Aquí está mi pseudo código, no estoy muy seguro sobre la inicialización> <

 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) 

preparándose para el algoritmo final …

Implementación de Java en funcionamiento de la secuencia de Palindrome más larga

 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)); } } 

import java.util.HashSet;

import java.util.Scanner;

/ ** * @param args * Se nos da una cadena y necesitamos encontrar la subsecuencia más larga en esa cadena que es palindrome * En este código hemos usado hashset para determinar el conjunto único de subcadena en las cadenas dadas * /

clase pública 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; } } 
 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]; } 

para cada letra en la cadena:

  • establece la letra como el medio del palíndromo (longitud actual = 1)

  • comprobar cuánto tiempo sería el palíndromo si este es su medio

  • si este palíndromo es más largo que el que encontramos (hasta ahora): conserve el índice y el tamaño del palíndromo.

O (N ^ 2): dado que tenemos un bucle que elije el medio y un bucle que verifica el tiempo del palíndromo si este es el medio. cada ciclo va de 0 a O (N) [el primero de 0 a N-1 y el segundo de 0 a (N-1) / 2]

por ejemplo: DBABCBA

i = 0: D es el centro del palíndromo, no puede ser más largo que 1 (ya que es el primero)

i = 1: B es el centro del palíndromo, verificar el carácter antes y después de B: no idéntico (D en un lado y A en el otro) -> longitud es 1.

i = 2: A está en el medio del palíndromo, revise el carácter antes y después de A: ambos B -> longitud es 3. revise caracteres con un espacio de 2: no identiacl (D en un lado y C en el otro) -> la longitud es 3.

etc.

Entrada: A1, A2, …., An

Objetivo: encontrar la subsecuencia más estrictamente creciente (no necesariamente contigua).

L (j): Subsecuencia estrictamente creciente más larga que termina en j

L (j): max{ L(i)}+1 } where i < j and A[i] < A[j]

A continuación, busque max{ L(j) } for all j

Obtendrás el código fuente aquí