Langste algemene vervolgsequentie

In deze tutorial leer je hoe de langste gemeenschappelijke subreeks wordt gevonden. Ook vind je werkende voorbeelden van de langste gemeenschappelijke subreeks in C, C ++, Java en Python.

De langste gemeenschappelijke subsequentie (LCS) wordt gedefinieerd als de langste subsubsequentie die gemeenschappelijk is voor alle gegeven sequenties, op voorwaarde dat de elementen van de subsequentie niet vereist zijn om opeenvolgende posities in te nemen binnen de originele sequenties.

Als S1 en S2 de twee gegeven sequenties zijn, dan is Z de gemeenschappelijke subreeks van S1 en S2 als Z een subreeks is van zowel S1 als S2. Verder moet Z een strikt stijgende reeks zijn van de indices van zowel S1 als S2.

In een strikt oplopende volgorde moeten de indices van de elementen die uit de oorspronkelijke sequenties worden gekozen in oplopende volgorde in Z staan.

Als

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

Het (A, D, B)kan dan geen subreeks zijn van S1, aangezien de volgorde van de elementen niet hetzelfde is (dwz niet strikt toenemende reeks).

Laten we LCS begrijpen met een voorbeeld.

Als

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

Dan zijn gewone subreeksen (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Onder deze subreeksen (C, D, A, C)is de langste gemeenschappelijke subreeks. We gaan deze langste gemeenschappelijke subreeks vinden met behulp van dynamisch programmeren.

Voordat u verder gaat, moet u dynamisch programmeren doorlopen als u nog geen kennis heeft van dynamisch programmeren.

Dynamische programmering gebruiken om de LCS te vinden

Laten we twee reeksen nemen:

De eerste reeks

Tweede reeks

De volgende stappen worden gevolgd om de langste gemeenschappelijke subreeks te vinden.

Maak een afmetingstabel n+1*m+1waarbij n en m respectievelijk de lengtes X en Y zijn. De eerste rij en de eerste kolom zijn gevuld met nullen. Initialiseer een tafel
Vul elke cel van de tabel met de volgende logica.
Als het teken dat overeenkomt met de huidige rij en de huidige kolom overeenkomen, vul dan de huidige cel door er een toe te voegen aan het diagonale element. Wijs een pijl naar de diagonale cel.
Neem anders de maximale waarde uit de vorige kolom en het vorige rijelement om de huidige cel te vullen. Wijs een pijl naar de cel met de maximale waarde. Als ze gelijk zijn, wijs ze dan aan. Vul de waarden in
Stap 2 wordt herhaald totdat de tafel is gevuld. Vul alle waarden in
De waarde in de laatste rij en de laatste kolom is de lengte van de langste gemeenschappelijke subreeks. De rechter benedenhoek is de lengte van de LCS
Om de langste gemeenschappelijke subreeks te vinden, begint u bij het laatste element en volgt u de richting van de pijl. De elementen die overeenkomen met () symbool vormen de langste gemeenschappelijke subreeks. Maak een pad volgens de pijlen

De langste gemeenschappelijke subreeks is dus CD.

LCS

Hoe is een dynamisch programmeeralgoritme efficiënter dan het recursieve algoritme bij het oplossen van een LCS-probleem?

De methode van dynamisch programmeren vermindert het aantal functieaanroepen. Het slaat het resultaat van elke functieaanroep op, zodat het in toekomstige oproepen kan worden gebruikt zonder dat er redundante oproepen nodig zijn.

In het bovenstaande dynamische algoritme worden de resultaten die zijn verkregen uit elke vergelijking tussen elementen van X en de elementen van Y opgeslagen in een tabel, zodat ze kunnen worden gebruikt in toekomstige berekeningen.

De tijd die een dynamische benadering nodig heeft, is dus de tijd die nodig is om de tafel te vullen (dwz. O (mn)). Terwijl het recursie-algoritme de complexiteit heeft van 2 ^{max (m, n)} .

Langste algemene volgalgoritme

 X en Y zijn twee gegeven reeksen Initialiseer een tabel LCS van dimensie X.lengte * Y.lengte X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Start van LCS ( 1) (1) Vergelijk X (i) en Y (j) Als X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Wijs een pijl naar LCS (i) (j) Anders LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Richt een pijl naar max (LCS (i-1) ( j), LCS (i) (j-1))

Python, Java en C / C ++ voorbeelden

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); )