Lengste vanlige påfølgende

I denne opplæringen vil du lære hvordan den lengste vanlige følgen blir funnet. Du vil også finne arbeidseksempler på den lengste vanlige konsekvensen i C, C ++, Java og Python.

Den lengste vanlige undersekvensen (LCS) er definert som den lengste undersekvensen som er felles for alle de gitte sekvensene, forutsatt at elementene i undersekvensen ikke kreves for å oppta påfølgende posisjoner i de originale sekvensene.

Hvis S1 og S2 er de to gitte sekvensene, er Z den vanlige undersekvensen til S1 og S2 hvis Z er en sekvens av både S1 og S2. Videre må Z være en strengt økende sekvens av indeksene til både S1 og S2.

I en streng økende sekvens må indeksene til elementene valgt fra de originale sekvensene være i stigende rekkefølge i Z.

Hvis

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

Da (A, D, B)kan ikke være en sekvens av S1 da rekkefølgen til elementene ikke er den samme (dvs. ikke strengt økende sekvens).

La oss forstå LCS med et eksempel.

Hvis

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

Deretter er vanlige påfølgende (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Blant disse konsekvensene (C, D, A, C)er den lengste vanlige konsekvensen. Vi skal finne denne lengste vanlige følgen ved hjelp av dynamisk programmering.

Før du går videre, hvis du ikke allerede vet om dynamisk programmering, kan du gå gjennom dynamisk programmering.

Bruke dynamisk programmering for å finne LCS

La oss ta to sekvenser:

Den første sekvensen

Second Sequence

Følgende trinn følges for å finne den lengste vanlige følgen.

Lag en tabell over dimensjoner n+1*m+1der n og m er lengdene på henholdsvis X og Y. Den første raden og den første kolonnen er fylt med nuller. Initialiser et bord
Fyll hver celle i tabellen ved hjelp av følgende logikk.
Hvis tegnet som tilsvarer gjeldende rad og gjeldende kolonne samsvarer, fyller du den nåværende cellen ved å legge en til det diagonale elementet. Pek en pil mot den diagonale cellen.
Ellers ta maksimumsverdien fra forrige kolonne og forrige radelement for å fylle den nåværende cellen. Pek en pil mot cellen med maksimal verdi. Hvis de er like, peker du på noen av dem. Fyll verdiene
Trinn 2 gjentas til tabellen er fylt. Fyll alle verdiene
Verdien i siste rad og siste kolonne er lengden på den lengste vanlige undersekvensen. Nederst til høyre er lengden på LCS
For å finne den lengste vanlige følgen, start fra det siste elementet og følg pilens retning. Elementene som tilsvarer () symbolet danner den lengste vanlige følgen. Lag en sti i henhold til pilene

Dermed er den lengste vanlige følgen CD.

LCS

Hvordan er en dynamisk programmeringsalgoritme mer effektiv enn den rekursive algoritmen mens man løser et LCS-problem?

Metoden for dynamisk programmering reduserer antall funksjonsanrop. Den lagrer resultatet av hvert funksjonsanrop slik at det kan brukes i fremtidige samtaler uten behov for overflødige samtaler.

I den ovennevnte dynamiske algoritmen lagres resultatene fra hver sammenligning mellom elementene i X og elementene i Y i en tabell slik at de kan brukes i fremtidige beregninger.

Så tiden det tar med en dynamisk tilnærming, er tiden det tar å fylle tabellen (dvs. O (mn)). Mens rekursjonsalgoritmen har kompleksiteten på 2 ^{maks (m, n)} .

Lengste vanlige påfølgende algoritme

 X og Y er to gitte sekvenser Initialiser en tabell LCS av dimensjon X. lengde * Y. lengde X. merke = X Y. merke = Y LCS (0) () = 0 LCS () (0) = 0 Start fra LCS ( 1) (1) Sammenlign X (i) og Y (j) Hvis X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Pek en pil mot LCS (i) (j) Ellers LCS (i) (j) = maks (LCS (i-1) (j), LCS (i) (j-1)) Pek en pil til maks (LCS (i-1) ( j), LCS (i) (j-1))

Python, Java og C / C ++ eksempler

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