comment trouver le plus long palindrome-séquence?

Question

Voici le problème (6.7 ch6 ) d'algorithmes livre (par Vazirani) qui diffère légèrement du problème classique que trouver le plus long palindrome. Comment puis-je résoudre ce problème?

Une sous est palindrome si elle est le même que lire de gauche à droite ou de droite à gauche. Par exemple, la séquence

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

a beaucoup palindromes séquences, y compris A,C,G,C,A et A,A,A,A (D'autre part, la sous-séquence A,C,T n'est pas palindrome). un legs un algorithme qui prend x[1 ...n] de séquence et retourne la (longueur de la) le plus long palindrome-séquence. Ses durée devrait être O(n^2)

Answer 1

Ceci peut être résolu en O (n ^ 2) en utilisant la programmation dynamique. Au fond, le problème est de construire le plus long palindrome en x[i...j] séquence en utilisant la plus longue pour x[i+1...j]-séquence, x[i,...j-1] et x[i+1,...,j-1] (si première et dernière lettres sont les mêmes).

Tout d'abord, la chaîne vide et une seule chaîne de caractères est trivialement un palindrome. Notez que pour une x[i,...,j] substring, si x[i]==x[j], on peut dire que la longueur de la plus longue palindrome est le plus long palindrome sur x[i+1,...,j-1]+2. Si elles ne correspondent pas, le plus long palindrome est le maximum de celui de x[i+1,...,j] et y[i,...,j-1].

Cela nous donne la fonction:

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

Vous pouvez simplement mettre en œuvre une version memoized de cette fonction, ou un code d'une table de la plus longue [i] fond [j] vers le haut.

Cela vous donne seulement la longueur de la plus longue séquence, pas la sous-séquence réelle elle-même. Mais il peut facilement être étendue à le faire aussi bien.

---

Answer 2

Ce problème peut également être fait comme une variation d'un problème très commun appelé le problème LCS (séquence sous Longest Common). Soit la chaîne d'entrée est représentée par un tableau de caractères s1 [0 ... n-1].

1) inverse la séquence donnée et stocker l'inverse dans un autre exemple de réseau s2 [0..n-1], qui est en substance s1 [n-1 .... 0]

2) LCS de la séquence s1 et s2 étant donné l'ordre inverse sera la plus longue séquence palindromique.

Cette solution est également une solution O (n ^ 2).

Answer 3

Il me fait un peu confus que la différence entre les sous-chaîne et sous- séquence. (Voir Ex6.8 et 6.11) Selon notre compréhension de séquence, l'exemple ne donnant pas le ACGCA palindrome-suite. Voici mon code pseudo, je ne suis pas tout à fait sûr de l'initialisation> <

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)

préparer l'algorithme final ...

Answer 4

Java de travail mise en œuvre de la séquence la plus longue 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 5

import java.util.HashSet;

import java.util.Scanner;

/ ** * @param args * On nous donne une chaîne et nous avons besoin de trouver la plus longue dans cette chaîne-séquence qui est palindrome * Dans ce code, nous avons utilisé HashSet afin de déterminer l'ensemble unique de sous-chaîne dans les chaînes données * /

{public class 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

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

pour chaque lettre dans la chaîne:

• définir la lettre comme le milieu du palindrome (Longueur courant = 1)

• vérifier combien de temps serait le palindrome si tel est son milieu

• si ce palindrome est plus long que celui que nous avons trouvé (jusqu'à présent). Garder l'index et la taille du palindrome

O (N ^ 2): puisque nous avons une boucle qui choisissent le milieu et une boucle qui contrôle la durée palindrome si tel est le milieu. chaque exécution de la boucle de 0 à O (N) [le premier de 0 à N-1 et le second est de 0 à (N-1) / 2]

par exemple: D B A B C B A

i = 0: D est le milieu du palindrome, ne peut pas être supérieure à 1 (car il est le premier)

i = 1: B est le milieu du palindrome, chèque de carbonisation avant et après B: pas identiques (D dans un côté et un de l'autre) -> longueur est 1.

i = 2: A est le milieu du palindrome, vérifier la carbonisation avant et après A: deux B -> la longueur est de 3. caractères de contrôle avec un espace de 2: pas identiacl (D dans un côté et C dans l'autre) -.> est la longueur 3

etc.

Answer 8

Entrée A1, A2, ...., An

Objectif:. Trouvez la plus longue séquence strictement croissante (pas nécessairement contiguës)

L (j): La plus longue séquence strictement croissante se terminant à j

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

Ensuite, trouvez max{ L(j) } for all j

Vous obtiendrez le code source