Längsta vanliga följd

I denna handledning lär du dig hur den längsta vanliga efterföljaren hittas. Du hittar också arbetsexempel på den längsta vanliga följden i C, C ++, Java och Python.

Den längsta gemensamma undersekvensen (LCS) definieras som den längsta sekvensen som är gemensam för alla givna sekvenser, förutsatt att elementen i sekvensen inte krävs för att uppta på varandra följande positioner inom de ursprungliga sekvenserna.

Om S1 och S2 är de två givna sekvenserna är Z den gemensamma sekvensen för S1 och S2 om Z är en sekvens av både S1 och S2. Dessutom måste Z vara en strikt ökande sekvens av indexen för både S1 och S2.

I en strikt ökande sekvens måste indexen för de element som valts från de ursprungliga sekvenserna vara i stigande ordning i Z.

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

Då (A, D, B)kan det inte vara en följd av S1 eftersom elementens ordning inte är densamma (dvs. inte strikt ökande sekvens).

Låt oss förstå LCS med ett exempel.

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

Sedan är vanliga följder (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Bland dessa följder (C, D, A, C)är den längsta vanliga följden. Vi kommer att hitta den längsta vanliga följden med hjälp av dynamisk programmering.

Innan du fortsätter, om du inte redan känner till dynamisk programmering, gå igenom dynamisk programmering.

Använda dynamisk programmering för att hitta LCS

Låt oss ta två sekvenser:

Den första sekvensen

andra sekvensen

Följande steg följs för att hitta den längsta vanliga följden.

Skapa en dimensionstabell n+1*m+1där n och m är längderna på X respektive Y. Den första raden och den första kolumnen är fyllda med nollor. Initiera ett bord
Fyll i varje cell i tabellen med följande logik.
Om tecknet som motsvarar den aktuella raden och den aktuella kolumnen matchar, fyll sedan den aktuella cellen genom att lägga till en i det diagonala elementet. Peka en pil mot den diagonala cellen.
Ta annars det maximala värdet från föregående kolumn och föregående radelement för att fylla den aktuella cellen. Peka en pil mot cellen med maximalt värde. Om de är lika, peka på någon av dem. Fyll värdena
Steg 2 upprepas tills tabellen är fylld. Fyll alla värden
Värdet i den sista raden och den sista kolumnen är längden på den längsta vanliga följden. Det nedre högra hörnet är längden på LCS
För att hitta den längsta vanliga följden, börja från det sista elementet och följ pilens riktning. Elementen som motsvarar () -symbolen utgör den längsta vanliga följden. Skapa en sökväg enligt pilarna

Således är den längsta vanliga följden CD.

LCS

Hur är en dynamisk programmeringsalgoritm effektivare än den rekursiva algoritmen när man löser ett LCS-problem?

Metoden för dynamisk programmering minskar antalet funktionssamtal. Det lagrar resultatet av varje funktionsanrop så att det kan användas i framtida samtal utan att det behövs överflödiga samtal.

I ovanstående dynamiska algoritm lagras resultaten från varje jämförelse mellan X-element och Y-elementen i en tabell så att de kan användas i framtida beräkningar.

Så, det tar en dynamisk inställning den tid det tar att fylla tabellen (dvs. O (mn)). Medan rekursionsalgoritmen har komplexiteten 2 ^{max (m, n)} .

Längsta vanliga följdalgoritm

 X och Y är två givna sekvenser Initiera en tabell LCS med dimension X. längd * Y. längd X. märke = X Y. märkning = Y LCS (0) () = 0 LCS () (0) = 0 Börja från LCS ( 1) (1) Jämför X (i) och Y (j) Om X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Peka en pil mot LCS (i) (j) Annars LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Peka en pil mot max (LCS (i-1) ( j), LCS (i) (j-1))

Python, Java och C / C ++ exempel

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