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

Question

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

Una subsecuencia es palindrómica si es lo mismo, ya sea leído de izquierda a derecha o 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, incluida A,C,G,C,A y A,A,A,A(Por otro lado, la subsecuencia A,C,T no es palindrómico). Idear un algoritmo que toma una secuencia x[1 ...n] y devuelve la (longitud de la) posterior subsecuencia palindrómica más larga. Su tiempo de ejecución debería ser O(n^2)

Answer 1

Esto se puede resolver en O (N^2) utilizando programación dinámica. Básicamente, el problema se trata de construir la posterior subsecuencia palindrómica más larga en x[i...j] Usando la más larga posterior para x[i+1...j], x[i,...j-1] y x[i+1,...,j-1] (Si las primeras y las últimas letras son las mismas).

En primer lugar, la cadena vacía y una sola cadena de caracteres 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. x[i+1,...,j-1]+2. Si no coinciden, el palíndromo más largo es el máximo de la de x[i+1,...,j] y y[i,...,j-1].

Esto nos da la función:

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

Simplemente puede implementar una versión memoizada de esa función, o codificar una tabla de más larga [i] [j] de abajo hacia arriba.

Esto le da solo la longitud de la posterior posterior más larga, no la posterior posterior en sí. Pero también se puede extender fácilmente para hacerlo.

---

Answer 2

Este problema también se puede hacer como una variación de un problema muy común llamado problema de LCS (subcuenca común más larga). Deje que la cadena de entrada esté representada por una matriz de caracteres S1 [0 ... N-1].

1) Invertir la secuencia dada y almacenar el reverso en otra matriz, digamos S2 [0..N-1], que en esencia es S1 [N-1 .... 0

2) Los LC de la secuencia dada S1 y la secuencia inversa S2 serán la secuencia palindrómica más larga.

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

Answer 3

Me confunde un poco que la diferencia entre la subcadena y la subsecuencia (ver EX6.8 y 6.11) de acuerdo con nuestra comprensión de la posterior, el ejemplo de donación no tiene la subsecuencia palindrómica ACGCA. Aquí está mi pseudo código, no estoy muy seguro de 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 la final del algoritmo ...

Answer 4

Implementación de Java en funcionamiento de la secuencia de palindromo 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));           
    }
}

Answer 5

import java.util.hashset;

import java.util.scanner;

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

Número de clase públicafpalindrome {

    /**
     * @param args
     * Given a string find the longest possible substring which is a palindrome.
     */
    public static HashSet<String> 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 6

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

Answer 7

Para cada letra en la cadena:

• Establezca la letra como el medio del palíndromo (longitud de corriente = 1)

• verifique 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): mantenga el índice y el tamaño del palíndromo.

O (n^2): dado que tenemos un bucle que elige el medio y un bucle que verifican cuánto tiempo el palíndromo es el medio. Cada bucle funciona de 0 a o (n) [el primero de 0 a N-1 y el segundo es de 0 a (N-1)/2

Por ejemplo: dbabcba

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

i = 1: B es el medio del palíndromo, verifique el char antes y después b: no idéntico (d en un lado y a en el otro) -> La longitud es 1.

i = 2: A es en el medio del palíndromo, verifique el char antes y después de A: Ambos B -> La longitud es 3. Verifique los caracteres con el espacio de 2: no identiAcl (d en un lado y c en el otro) ->> La longitud es 3.

etc.

Answer 8

Aporte : A1, a2, ...., un

Meta : Encuentre la posterior subsecuencia estrictamente más larga (no necesariamente contigua).

L (J): La subsecuencia estrictamente más larga que termina en J

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

Entonces busca max{ L(j) } for all j

Obtendrá el código fuente aquí