jak znaleźć najdłuższą podciąć palindromów?

Question

Oto problem (6.7 ch6) z książki Algorithms (autorstwa Vazirani), która nieznacznie różni się od klasycznego problemu, który jest finding longest palindrome. Jak mogę rozwiązać ten problem?

podciąg jest palindromiczna jeśli jest samo czy odczytu od lewej do prawej lub prawej do lewej. Na przykład, sekwencja

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

ma wiele palindromową podsekwencje tym A,C,G,C,A i A,A,A,A (drugiej strony, podciąg A,C,T nie są palindromowe). Opracuj algorytm , który przyjmuje sekwencję x[1 ...n] i zwraca (najdłuższy) najdłuższy podtyp palinowy. Jego czas pracy powinien być O(n^2)

Answer 1

ten może być rozwiązany w O (N^2) z zastosowaniem dynamicznego programowania. Zasadniczo, problem polega na zbudowaniu najdłuższej podciągu palindromowego w x[i...j] przy użyciu najdłuższego podciągu dla x[i+1...j], x[i,...j-1] i x[i+1,...,j-1] (jeśli pierwsza i ostatnia litera są takie same).

Po pierwsze, pusty ciąg i pojedynczy ciąg znaków to banalnie palindrom. Należy zauważyć, że dla podłańcucha x[i,...,j], jeśli x[i]==x[j], możemy powiedzieć, że długość najdłuższego palindromu jest najdłuższym palindromem nad x[i+1,...,j-1]+2.Jeśli nie pasują, najdłuższy palindrom wynosi maksimum x[i+1,...,j] i y[i,...,j-1].

To daje nam funkcję:

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 

Można po prostu wdrożyć memoized wersję tej funkcji, lub kod tabelę najdłuższej [i] [j] oddolnie.

Daje to tylko długość najdłuższego podciągu, a nie sam podciąg. Ale można go łatwo rozszerzyć, aby to zrobić.

---

Answer 2

dla każdej litery w łańcuchu:

• ustawić list jako środku palindrom (aktualna długość = 1)

• sprawdzić jak długo byłby palindromem, jeśli jest to jego środkowy obiekt, jeśli ten palindrom jest dłuższy niż ten, który znaleźliśmy (do tej pory): zachowaj indeks i wielkość palindromu.

O (N^2): ponieważ mamy jedną pętlę, która wybiera środkową i jedną pętlę, która sprawdza długość palindromu, jeśli jest to środek. Każda pętla wynosi od 0 do O (n) [pierwszego od 0 do n-1, a drugi oznacza liczbę od 0 do (N-1)/2]

na przykład: DBABCBA

I = 0: D jest środkiem palindromu, nie może być dłuższy niż 1 (ponieważ jest to pierwszy)

i = 1: B jest środkiem palindromu, sprawdź znak przed i po B: nie identyczny (D z jednej strony i A z drugiej) -> długość wynosi 1.

i = 2: A jest środkiem palindromu, sprawdź znak przed i po A: oba B -> długość to 3. sprawdź znaki z przerwą 2: nie identiacl (D z jednej strony i C, w drugiej) -> długość 3.

itp

Answer 3

Wejście: A1, A2, .... An

Cel: Znajdź najdłuższą ściśle rosnącą podciąg (niekoniecznie ciągły).

L (j): Najdłuższy ściśle zwiększenie podciąg kończąc na j

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

Następnie znajdź max{ L(j) } for all j

dostaniesz kod źródłowy here

Answer 4

Praca Java Implementacja najdłuższej sekwencji palindromowej

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

To sprawia, że ​​jestem trochę zdezorientowany, że różnica między podciągu i podciągu. (Patrz Ex6.8 i 6.11) Według naszego rozumienia podciągu, nadania przykład nie ma palindromową podciąg ACGCA. Oto mój pseudo kod, nie jestem pewien, o inicjalizacji> <

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) 

przygotowuje się do finału algorytm ...

Answer 6

Ten problem może być również wykonane jako odmiana bardzo częstym problemem zwany problemem podrzędnym LCS (Longest Common Sub sequence). Niech łańcuch wejściowy będzie reprezentowany przez tablicę znaków s1 [0 ... n-1].

1), do tyłu danej sekwencji a przechowuje odwrotne w innej tablicy mówią s2 [0..n-1], która w istocie jest S1 [n-1 .... 0]

2) LCS z podana sekwencja s1 i odwrotna sekwencja s2 będą najdłuższą sekwencją palindromową.

To rozwiązanie jest również rozwiązaniem O (n^2).

Answer 7

import java.util.HashSet;

import java.util.Skaner;

/** * @param args * Dane są ciągiem i musimy znaleźć najdłuższy podciąg w tego łańcucha, który jest palindrom * W tym kodzie użyliśmy hashset w celu ustalenia unikalny zestaw podciąg w podanych ciągów */

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