Najduža česta sljedba

U ovom vodiču naučit ćete kako se pronalazi najduža zajednička podsljedica. Također, pronaći ćete i radne primjere najduže zajedničke podsekcije u C, C ++, Java i Python.

Najduža zajednička podsljedica (LCS) definira se kao najdulja podsljeda koja je zajednička svim zadanim sekvencama, pod uvjetom da elementi podsljeda ne trebaju zauzimati uzastopne položaje unutar izvornih sekvenci.

Ako su S1 i S2 dvije zadane sekvence, tada je Z zajednička podsljedica S1 i S2 ako je Z podsekvenca i S1 i S2. Nadalje, Z mora biti strogo rastuća sekvenca indeksa i S1 i S2.

U strogo rastućem slijedu, indeksi elemenata izabranih iz izvornih nizova moraju biti u uzlaznom redoslijedu u Z.

Ako

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

Tada, (A, D, B)ne može biti podsljedica S1 jer redoslijed elemenata nije isti (tj. Ne strogo rastuća sekvenca).

Razumijemo LCS na primjeru.

Ako

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

Tada su uobičajene sljednice (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Među tim podsljedicama (C, D, A, C)nalazi se i najduža uobičajena podzadaća. Pronaći ćemo ovu najdužu zajedničku podsljedicu pomoću dinamičkog programiranja.

Prije nego što nastavite dalje, ako već ne znate dinamičko programiranje, prođite kroz dinamičko programiranje.

Korištenje dinamičkog programiranja za pronalaženje LCS-a

Uzmimo dvije sekvence:

Prva sekvenca

Druga sekvenca

Slijede koraci za pronalaženje najdužeg zajedničkog slijeda.

Stvorite tablicu dimenzija n+1*m+1gdje su n i m duljine X odnosno Y. Prvi redak i prvi stupac ispunjeni su nulama. Inicirajte tablicu
Ispunite svaku ćeliju tablice slijedeći logiku.
Ako se znak koji odgovara trenutnom retku i trenutnom stupcu podudara, ispunite trenutnu ćeliju dodavanjem jedne dijagonalnom elementu. Usmjerite strelicu na dijagonalnu ćeliju.
Inače uzimaju maksimalnu vrijednost iz prethodnog stupca i prethodnog elementa retka za popunjavanje trenutne ćelije. Usmjerite strelicu na ćeliju s maksimalnom vrijednošću. Ako su jednaki, pokažite na bilo kojeg od njih. Ispunite vrijednosti
Korak 2 ponavlja se sve dok se tablica ne popuni. Ispunite sve vrijednosti
Vrijednost u posljednjem retku i posljednjem stupcu duljina je najdužeg zajedničkog slijeda. Donji desni kut je duljina LCS-a
Da biste pronašli najdužu zajedničku podsljedicu, krenite od posljednjeg elementa i slijedite smjer strelice. Elementi koji odgovaraju simbolu () tvore najdulju zajedničku podsljedicu. Stvorite put prema strelicama

Dakle, najduža uobičajena podljednica je CD.

LCS

Kako je algoritam dinamičkog programiranja učinkovitiji od rekurzivnog algoritma tijekom rješavanja LCS problema?

Metoda dinamičkog programiranja smanjuje broj poziva funkcija. Pohranjuje rezultat svakog poziva funkcije tako da se može koristiti u budućim pozivima bez potrebe za suvišnim pozivima.

U gore navedenom dinamičkom algoritmu, rezultati dobiveni svakom usporedbom između elemenata X i elemenata Y pohranjeni su u tablicu kako bi se mogli koristiti u budućim proračunima.

Dakle, vrijeme potrebno dinamičnom pristupu je vrijeme potrebno za popunjavanje tablice (tj. O (mn)). Dok algoritam rekurzije ima složenost od 2 ^{max (m, n)} .

Najdulji uobičajeni algoritam slijeda

 X i Y su dva zadana slijeda Inicijalizirajte tablicu LCS dimenzije X.duljina * Y.duljina X.oznaka = X Y.oznaka = Y LCS (0) () = 0 LCS () (0) = 0 Počnite od LCS ( 1) (1) Usporedite X (i) i Y (j) Ako je X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Usmjerite strelicu na LCS (i) (j) Inače LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Usmjerite strelicu na max (LCS (i-1) ( j), LCS (i) (j-1))

Primjeri Pythona, 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); )