algorithm - secuencia - palindromos ejemplos

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

Question

Aquí está el problema (6.7 ch6 ) del libro Algorithms (por Vazirani) que difiere ligeramente del problema clásico que es 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, incluyendo A,C,G,C,A y A,A,A,A (por otra parte, 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)

Answer 1

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

1) Invierta la secuencia dada y almacene el inverso en otra matriz, digamos s2 [0..n-1] que en esencia es s1 [n-1 .... 0]

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

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

Answer 2

Esto se puede resolver en O (n ^ 2) usando la programació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] x[i+1,...,j-1] (si la primera y la última letra son las mismas).

En primer lugar, la cadena vacía y una cadena de un solo carácter son trivialmente un palíndromo. Note 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 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 memorizada de esa función, o codificar una tabla de la más larga [i] [j] de abajo hacia arriba.

Esto le proporciona solo la longitud de la subsecuencia más larga, no la subsecuencia real en sí. Pero puede extenderse fácilmente para hacer eso también.

Answer 3

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

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 4

Me confunde un poco 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 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)

preparando para el algoritmo final ...

Answer 5

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 palíndromo * En este código hemos usado hashset para determinar el conjunto único de subcadenas 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<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

para cada letra en la cadena:

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

• Compruebe 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): ya que tenemos un bucle que elige el medio y un bucle que verifica cuánto tiempo dura el palíndromo si este es el medio. cada bucle se ejecuta 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 la mitad del palíndromo, no puede ser más largo que 1 (ya que es el primero)

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

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

etc.

Answer 7

Entrada: A1, A2, ...., An

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

L (j): la subsecuencia estrictamente más larga y larga que termina en j

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

Luego encuentra max{ L(j) } for all j

Obtendrá el código fuente here

Answer 8

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