so finden längste Palindrom Teilfolge?

Question

Hier ist das problem (6.7 ch6 ) von Algorithmen Buch (Vazirani), dass etwas unterscheidet sich von den klassischen problem, dass finden längste Palindrom.Wie kann ich dieses problem lösen ?

Eine Teilfolge ist Palindrom, wenn es ist egal ob von Links nach rechts gelesen oder von rechts nach Links.Für Beispiel, die Reihenfolge

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

hat viele Palindrom untersequenzen, einschließlich A,C,G,C,A und A,A,A,A (auf der anderen Seite, die Teilfolge A,C,T ist nicht Palindrom).Bei der Konzeption eines Algorithmus nimmt eine Sequenz x[1 ...n] und gibt die (Länge der) längste Palindrom Teilfolge.Seine Laufzeit sein sollte O(n^2)

Answer 1

Dies kann in O (n^2) unter Verwendung einer dynamischen Programmierung gelöst werden. Grundsätzlich besteht das Problem darum, die längste palindromische Subsequence in zu bauen x[i...j] Verwenden der längsten Subsequenz für x[i+1...j], x[i,...j-1] und x[i+1,...,j-1] (Wenn die ersten und letzten Buchstaben gleich sind).

Erstens ist die leere Schnur und eine einzelne Zeichenfolge trivial ein Palindrom. Beachten Sie das für ein Substring x[i,...,j], wenn x[i]==x[j], Wir können sagen, dass die Länge des längsten Palindroms das längste Palindrom ist x[i+1,...,j-1]+2. Wenn sie nicht übereinstimmen, ist das längste Palindrom das Maximum von dem von x[i+1,...,j] und y[i,...,j-1].

Dies gibt uns die Funktion:

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

Sie können einfach eine memoisierte Version dieser Funktion implementieren oder eine Tabelle mit längsten [i] [j] unten nach oben codieren.

Dies gibt Ihnen nur die Länge der längsten Subsequenz, nicht die tatsächliche Untersequenz selbst. Aber es kann leicht erweitert werden, um dies zu tun.

---

Answer 2

Dieses Problem kann auch als Variation eines sehr häufigen Problems als LCS -Problem (längst gemeinsame Subsequenz) durchgeführt werden. Lassen Sie die Eingangszeichenfolge durch ein Zeichenarray S1 [0 ... n-1] dargestellt.

1) Umkehren der angegebenen Sequenz und speichern Sie das Gegenteil in einem anderen Array, sagen Sie S2 [0..N-1], was im Wesentlichen S1 [n-1 .... 0] ist

2) LCs der gegebenen Sequenz S1 und der Reverse -Sequenz S2 sind die längste palindromische Sequenz.

Diese Lösung ist auch eine O (n^2) Lösung.

Answer 3

Es macht mich ein wenig verwirrt, dass der Unterschied zwischen Substring und Subsequenz (siehe EX6.8 und 6.11) Gemäß unserem Verständnis der Subsequence hat das ggebene Beispiel nicht die palindromische Subsequenz -ACGCA. Hier ist mein Pseudocode, ich bin mir nicht ganz sicher über die Initialisierung>

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)

Vorbereitung auf den Algorithmus Finale ...

Answer 4

Arbeiten Java -Implementierung der längsten Palindrome -Sequenz

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 * Wir erhalten eine Zeichenfolge und müssen die längste Sequenz in der Zeichenfolge finden, die Palindrome * in diesem Code verwendet hat, den wir verwendet haben, um den eindeutigen Substring -Satz in den angegebenen Zeichenfolgen zu bestimmen */

öffentliche KlassennummerOfPalindrome {

    /**
     * @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

für jeden Buchstaben in der Zeichenfolge:

• stellen Sie den Buchstaben als die Mitte der palindrome (aktuelle Länge = 1)

• prüfen Sie, wie lange würden die Palindrom, wenn das ist Ihre Mitte

• wenn dieses Palindrom ist länger als die, die wir gefunden (bis jetzt) :halten Sie die index-und die Größe der palindrome.

O(N^2) :da haben wir eine Schleife, wählen Sie die Mitte und eine Schleife, die überprüfen, wie lange das Palindrom ist dies die Mitte.jede Schleife läuft von 0 bis O(N) [der erste von 0 bis N-1, und das zweite ist von 0 bis (N-1)/2]

zum Beispiel:D B A B C B A

i=0 :D ist die Mitte, das Palindrom, kann nicht länger sein als 1 ist (da es das erste)

i=1:B ist die Mitte der palindrome, überprüfen char vor und nach B :nicht identisch (D in einer Seite und Eine in der anderen) - > Länge 1 ist.

i=2 :Eine ist mitten in der Palindrom, überprüfen char vor und nach :beide B - > Länge ist 3.überprüfen chars mit Rückstand von 2:nicht identiacl (D, auf der einen Seite und C in die andere) - > Länge ist 3.

etc.

Answer 8

Eingabe: A1, a2, ...., a

Tor : Finden Sie die längste streng zunehmende Subsequenz (nicht unbedingt angrenzend).

L (j): Die längste streng zunehmende Subsequenz, die bei J endet

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

Dann finden max{ L(j) } for all j

Sie erhalten den Quellcode hier