A leghosszabb közös következmény

Ebben az oktatóanyagban megtudhatja, hogyan található a leghosszabb közös folytatás. Ezenkívül talál működő példákat a C, C ++, a Java és a Python leghosszabb közös szakaszára.

A leghosszabb közös szekvencia (LCS) a leghosszabb szekvencia, amely az összes adott szekvencián közös, feltéve, hogy a szekvencia elemeinek nem szükséges egymást követő pozíciókat elfoglalniuk az eredeti szekvenciákon belül.

Ha S1 és S2 a két megadott szekvencia, akkor Z az S1 és S2 közös alszekvenciája, ha Z mind S1, mind S2 alszekvenciája. Ezenkívül Z-nek szigorúan növekvő szekvenciának kell lennie mind az S1, mind az S2 indexeiről.

Szigorúan növekvő sorrendben az eredeti szekvenciák közül kiválasztott elemek indexeinek Z-ben növekvő sorrendben kell lenniük.

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

Ezután (A, D, B)nem lehet az S1 folytatása, mivel az elemek sorrendje nem azonos (azaz nem szigorúan növekvő sorrend).

Értsük meg az LCS-t egy példával.

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

Ezután a közös alszekvenciák (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Ezek között a szekvenciák (C, D, A, C)közül a leghosszabb a közös. Ezt a leghosszabb közös alszakaszt fogjuk megtalálni dinamikus programozással.

A továbblépés előtt, ha még nem ismeri a dinamikus programozást, kérjük, menjen át a dinamikus programozáson.

A dinamikus programozás használata az LCS megtalálásához

Vegyünk két szekvenciát:

Az első szekvencia

második szekvencia

A következő lépéseket követi a leghosszabb közös folytatás megtalálásához.

Hozzon létre egy dimenziótáblát, n+1*m+1ahol n és m X, illetve Y hossza. Az első sor és az első oszlop nullákkal van kitöltve. Inicializáljon egy táblázatot
Töltse ki a táblázat minden celláját a következő logika segítségével.
Ha az aktuális sornak és az aktuális oszlopnak megfelelő karakter megfelel, akkor töltse ki az aktuális cellát úgy, hogy egyet hozzáad az átlós elemhez. Mutasson egy nyíl az átlós cellára.
Else vegye az előző oszlop és az előző sor elem maximális értékét az aktuális cella kitöltéséhez. Mutasson egy nyilat a maximális értékű cellára. Ha egyenlőek, mutasson bármelyikre. Töltse ki az értékeket
A 2. lépést addig ismételjük, amíg a táblázat meg nem telik. Töltse ki az összes értéket
Az utolsó sor és az utolsó oszlop értéke a leghosszabb közös alsor hossza. A jobb alsó sarok az LCS hossza
A leghosszabb közös folytatás megtalálásához kezdje az utolsó elemet, és kövesse a nyíl irányát. A () szimbólumnak megfelelő elemek alkotják a leghosszabb közös folytatást. Hozzon létre egy utat a nyilak szerint

Így a leghosszabb közös szakasz a CD.

LCS

Hogyan lehet hatékonyabb a dinamikus programozási algoritmus, mint a rekurzív algoritmus az LCS-probléma megoldása közben?

A dinamikus programozás módja csökkenti a függvényhívások számát. Minden függvényhívás eredményét tárolja, hogy a jövőbeni hívásokban redundáns hívások nélkül is felhasználható legyen.

A fenti dinamikus algoritmusban az X és Y elemei minden egyes összehasonlításából származó eredményeket egy táblázatban tároljuk, hogy felhasználhatók legyenek a későbbi számításokban.

Tehát a dinamikus megközelítés által elvárt idő a táblázat kitöltéséhez szükséges idő (azaz O (mn)). Míg a rekurziós algoritmus bonyolultsága 2 ^{max (m, n)} .

A leghosszabb közös utólagos algoritmus

 X és Y két megadott szekvencia Inicializálja az X dimenziós LCS táblázatot. Hosszúság * Y.hossz X.címke = X Y.címke = Y LCS (0) () = 0 LCS () (0) = 0 Indítsa el az LCS-től ( 1) (1) Hasonlítsa össze az X (i) és az Y (j) pontokat, ha X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Mutasson egy nyílra az LCS-re (i) (j) Egyéb LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Mutasson egy nyíl maximumra (LCS (i-1) ( j), LCS (i) (j-1))

Példák Python, Java és 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); )