Successione comune più lunga

In questo tutorial imparerai come trovare la sottosequenza comune più lunga. Inoltre, troverai esempi funzionanti della sottosequenza comune più lunga in C, C ++, Java e Python.

La sottosequenza comune più lunga (LCS) è definita come la sottosequenza più lunga comune a tutte le sequenze date, a condizione che gli elementi della sottosequenza non siano tenuti a occupare posizioni consecutive all'interno delle sequenze originali.

Se S1 e S2 sono le due sequenze date, Z è la sottosequenza comune di S1 e S2 se Z è una sottosequenza sia di S1 che di S2. Inoltre, Z deve essere una sequenza strettamente crescente degli indici di S1 e S2.

In una sequenza rigorosamente crescente, gli indici degli elementi scelti dalle sequenze originali devono essere in ordine crescente in Z.

 S1 = (B, C, D, A, A, C, D)

Quindi, (A, D, B)non può essere una sottosequenza di S1 poiché l'ordine degli elementi non è lo stesso (cioè una sequenza non strettamente crescente).

Cerchiamo di capire LCS con un esempio.

 S1 = (B, C, D, A, A, C, D) S2 = (A, C, D, B, A, C)

Quindi, le sottosequenze comuni sono (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Tra queste (C, D, A, C)sottosequenze , è la sottosequenza comune più lunga. Troveremo questa sottosequenza comune più lunga usando la programmazione dinamica.

Prima di procedere oltre, se non si conosce già la programmazione dinamica, passare alla programmazione dinamica.

Utilizzo della programmazione dinamica per trovare LCS

Prendiamo due sequenze:

La prima sequenza

Seconda sequenza

I seguenti passaggi sono seguiti per trovare la sottosequenza comune più lunga.

Crea una tabella di dimensione n+1*m+1dove n e m sono le lunghezze di X e Y rispettivamente. La prima riga e la prima colonna vengono riempite con zeri. Inizializza una tabella
Riempi ogni cella della tabella utilizzando la seguente logica.
Se il carattere corrispondente alla riga corrente e la colonna corrente corrispondono, riempire la cella corrente aggiungendone uno all'elemento diagonale. Punta una freccia sulla cella diagonale.
Altrimenti prendi il valore massimo dalla colonna precedente e dall'elemento riga precedente per riempire la cella corrente. Punta una freccia sulla cella con il valore massimo. Se sono uguali, indica uno di loro. Riempi i valori
Il passaggio 2 viene ripetuto fino a riempire la tabella. Riempi tutti i valori
Il valore nell'ultima riga e nell'ultima colonna è la lunghezza della sottosequenza comune più lunga. L'angolo in basso a destra è la lunghezza dell'LCS
Per trovare la sottosequenza comune più lunga, iniziare dall'ultimo elemento e seguire la direzione della freccia. Gli elementi corrispondenti al simbolo () formano la sottosequenza comune più lunga. Crea un percorso in base alle frecce

Pertanto, la sottosequenza comune più lunga è CD.

LCS

In che modo un algoritmo di programmazione dinamica è più efficiente dell'algoritmo ricorsivo durante la risoluzione di un problema LCS?

Il metodo di programmazione dinamica riduce il numero di chiamate di funzione. Memorizza il risultato di ogni chiamata di funzione in modo che possa essere utilizzato in chiamate future senza la necessità di chiamate ridondanti.

Nell'algoritmo dinamico di cui sopra, i risultati ottenuti da ogni confronto tra gli elementi di X e gli elementi di Y sono memorizzati in una tabella in modo che possano essere utilizzati in calcoli futuri.

Quindi, il tempo impiegato da un approccio dinamico è il tempo impiegato per riempire la tabella (es. O (mn)). Al contrario, l'algoritmo di ricorsione ha la complessità di 2 ^{max (m, n)} .

Algoritmo di successione comune più lungo

 X e Y sono due sequenze date Inizializza una tabella LCS di dimensione X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Inizia da LCS ( 1) (1) Confronta X (i) e Y (j) Se X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Punta una freccia verso LCS (i) (j) Else LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Punta una freccia verso max (LCS (i-1) ( j), LCS (i) (j-1))

Esempi di Python, Java e C / C ++

Python Java C C ++

 # The longest common subsequence in Python # Function to find lcs_algo def lcs_algo(S1, S2, m, n): L = ((0 for x in range(n+1)) for x in range(m+1)) # Building the mtrix in bottom-up way for i in range(m+1): for j in range(n+1): if i == 0 or j == 0: L(i)(j) = 0 elif S1(i-1) == S2(j-1): L(i)(j) = L(i-1)(j-1) + 1 else: L(i)(j) = max(L(i-1)(j), L(i)(j-1)) index = L(m)(n) lcs_algo = ("") * (index+1) lcs_algo(index) = "" i = m j = n while i> 0 and j> 0: if S1(i-1) == S2(j-1): lcs_algo(index-1) = S1(i-1) i -= 1 j -= 1 index -= 1 elif L(i-1)(j)> L(i)(j-1): i -= 1 else: j -= 1 # Printing the sub sequences print("S1 : " + S1 + "S2 : " + S2) print("LCS: " + "".join(lcs_algo)) S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)

 // The longest common subsequence in Java class LCS_ALGO ( static void lcs(String S1, String S2, int m, int n) ( int()() LCS_table = new int(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1.charAt(i - 1) == S2.charAt(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = Math.max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); int temp = index; char() lcs = new char(index + 1); lcs(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1.charAt(i - 1) == S2.charAt(j - 1)) ( lcs(index - 1) = S1.charAt(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences System.out.print("S1 : " + S1 + "S2 : " + S2 + "LCS: "); for (int k = 0; k <= temp; k++) System.out.print(lcs(k)); System.out.println(""); ) public static void main(String() args) ( String S1 = "ACADB"; String S2 = "CBDA"; int m = S1.length(); int n = S2.length(); lcs(S1, S2, m, n); ) )

 // The longest common subsequence in C #include #include int i, j, m, n, LCS_table(20)(20); char S1(20) = "ACADB", S2(20) = "CBDA", b(20)(20); void lcsAlgo() ( m = strlen(S1); n = strlen(S2); // Filling 0's in the matrix for (i = 0; i <= m; i++) LCS_table(i)(0) = 0; for (i = 0; i <= n; i++) LCS_table(0)(i) = 0; // Building the mtrix in bottom-up way for (i = 1; i <= m; i++) for (j = 1; j = LCS_table(i)(j - 1)) ( LCS_table(i)(j) = LCS_table(i - 1)(j); ) else ( LCS_table(i)(j) = LCS_table(i)(j - 1); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences printf("S1 : %s S2 : %s ", S1, S2); printf("LCS: %s", lcsAlgo); ) int main() ( lcsAlgo(); printf(""); )

 // The longest common subsequence in C++ #include using namespace std; void lcsAlgo(char *S1, char *S2, int m, int n) ( int LCS_table(m + 1)(n + 1); // Building the mtrix in bottom-up way for (int i = 0; i <= m; i++) ( for (int j = 0; j <= n; j++) ( if (i == 0 || j == 0) LCS_table(i)(j) = 0; else if (S1(i - 1) == S2(j - 1)) LCS_table(i)(j) = LCS_table(i - 1)(j - 1) + 1; else LCS_table(i)(j) = max(LCS_table(i - 1)(j), LCS_table(i)(j - 1)); ) ) int index = LCS_table(m)(n); char lcsAlgo(index + 1); lcsAlgo(index) = ''; int i = m, j = n; while (i> 0 && j> 0) ( if (S1(i - 1) == S2(j - 1)) ( lcsAlgo(index - 1) = S1(i - 1); i--; j--; index--; ) else if (LCS_table(i - 1)(j)> LCS_table(i)(j - 1)) i--; else j--; ) // Printing the sub sequences cout << "S1 : " << S1 << "S2 : " << S2 << "LCS: " << lcsAlgo << ""; ) int main() ( char S1() = "ACADB"; char S2() = "CBDA"; int m = strlen(S1); int n = strlen(S2); lcsAlgo(S1, S2, m, n); )