Cea mai lungă consecință comună

În acest tutorial, veți afla cum se găsește cea mai lungă subsecvență comună. De asemenea, veți găsi exemple de lucru ale celei mai lungi subsecvențe comune în C, C ++, Java și Python.

Cea mai lungă subsecvență comună (LCS) este definită ca cea mai lungă subsecvență comună tuturor secvențelor date, cu condiția ca elementele subsecvenței să nu fie obligate să ocupe poziții consecutive în secvențele originale.

Dacă S1 și S2 sunt cele două secvențe date, Z este subsecvența comună a S1 și S2 dacă Z este o subsecvență atât a S1 cât și a S2. Mai mult, Z trebuie să fie o secvență strict crescătoare a indicilor atât ai S1, cât și ai S2.

Într-o secvență strict crescătoare, indicii elementelor alese din secvențele originale trebuie să fie în ordine crescătoare în Z.

Dacă

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

Apoi, (A, D, B)nu poate fi o subsecvență a lui S1, deoarece ordinea elementelor nu este aceeași (adică o secvență care nu crește strict).

Să înțelegem LCS cu un exemplu.

Dacă

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

Apoi, subsecvențele comune sunt (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Printre aceste subsecvențe, (C, D, A, C)se află cea mai lungă subsecvență comună. Vom găsi această cea mai lungă subsecvență comună folosind programarea dinamică.

Înainte de a continua, dacă nu știți deja despre programarea dinamică, vă rugăm să parcurgeți programarea dinamică.

Utilizarea programării dinamice pentru a găsi LCS

Să luăm două secvențe:

Prima secvență a

doua secvență

Următorii pași sunt urmați pentru a găsi cea mai lungă subsecvență comună.

Creați un tabel de dimensiuni n+1*m+1unde n și m sunt lungimile lui X și respectiv Y. Primul rând și prima coloană sunt umplute cu zerouri. Inițializați un tabel
Completați fiecare celulă a tabelului utilizând următoarea logică.
Dacă caracterul care corespunde rândului curent și coloanei curente se potrivește, atunci umpleți celula curentă adăugând una la elementul diagonal. Îndreptați o săgeată către celula diagonală.
Altfel, luați valoarea maximă din coloana anterioară și elementul rând anterior pentru umplerea celulei curente. Îndreptați o săgeată spre celulă cu valoarea maximă. Dacă sunt egali, indicați pe oricare dintre ei. Completați valorile
Pasul 2 se repetă până când masa este umplută. Completați toate valorile
Valoarea din ultimul rând și ultima coloană este lungimea celei mai lungi subsecvențe comune. Colțul din dreapta jos este lungimea LCS
Pentru a găsi cea mai lungă subsecvență comună, începeți de la ultimul element și urmați direcția săgeții. Elementele corespunzătoare simbolului () formează cea mai lungă subsecvență comună. Creați o cale conform săgeților

Astfel, cea mai lungă subsecvență comună este CD.

LCS

Cum este un algoritm de programare dinamică mai eficient decât algoritmul recursiv în timp ce rezolvă o problemă LCS?

Metoda de programare dinamică reduce numărul de apeluri funcționale. Stochează rezultatul fiecărui apel funcțional, astfel încât să poată fi utilizat în apeluri viitoare fără a fi nevoie de apeluri redundante.

În algoritmul dinamic de mai sus, rezultatele obținute din fiecare comparație între elementele lui X și elementele lui Y sunt stocate într-un tabel, astfel încât să poată fi utilizate în calculele viitoare.

Deci, timpul luat de o abordare dinamică este timpul necesar pentru a umple tabelul (adică O (mn)). În timp ce algoritmul de recursivitate are complexitatea de 2 ^{max (m, n)} .

Cel mai lung algoritm de subsecvență comună

 X și Y să fie două secvențe date Inițializați un tabel LCS cu dimensiunea X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Începeți de la LCS ( 1) (1) Comparați X (i) și Y (j) Dacă X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Îndreptați o săgeată către LCS (i) (j) Altele LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Îndreptați o săgeată spre max (LCS (i-1) ( j), LCS (i) (j-1))

Exemple Python, Java și 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); )