Najdaljša pogosta naslednja

V tej vadnici boste izvedeli, kako je najdeno najdaljše skupno podtočje. Prav tako boste našli delovne primere najdaljšega skupnega zaporedja v C, C ++, Java in Python.

Najdaljše skupno zaporedje (LCS) je opredeljeno kot najdaljše podpoglavje, ki je skupno vsem danim zaporedjem, pod pogojem, da elementi podsekvence ne smejo zasedati zaporednih položajev znotraj prvotnih zaporedij.

Če sta S1 in S2 dano zaporedje, potem je Z skupno podrejevanje S1 in S2, če je Z podsekvenca obeh S1 in S2. Poleg tega mora biti Z strogo naraščajoče zaporedje indeksov S1 in S2.

V strogo naraščajočem zaporedju morajo biti indeksi elementov, izbranih med prvotnimi zaporedji, v Z naraščajočem zaporedju.

Če

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

Nato (A, D, B)ne more biti podsekvenca S1, saj vrstni red elementov ni enak (tj. Ne strogo naraščajoče zaporedje).

Dovolite nam, da razumemo LCS s primerom.

Če

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

Potem so običajne podpoje (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Med temi podsekvencami (C, D, A, C)je najdaljša pogosta podpolja. To najdaljše skupno zaporedje bomo našli z uporabo dinamičnega programiranja.

Preden nadaljujete, če še ne poznate dinamičnega programiranja, pojdite na dinamično programiranje.

Uporaba dinamičnega programiranja za iskanje LCS

Vzemimo dve zaporedji:

Prvo zaporedje

Drugo zaporedje

Sledijo naslednji koraki za iskanje najdaljšega skupnega podsekvence.

Ustvarite tabelo dimenzij, n+1*m+1kjer sta n in m dolžini X oziroma Y. Prva vrstica in prvi stolpec sta zapolnjena z ničlami. Inicializirajte tabelo
Izpolnite vsako celico tabele z naslednjo logiko.
Če se znak, ki ustreza trenutni vrstici in trenutnemu stolpcu, ujemata, zapolnite trenutno celico tako, da jo v diagonalni element dodate. Usmerite puščico proti diagonalni celici.
V nasprotnem primeru vzemite največjo vrednost iz prejšnjega stolpca in prejšnjega elementa vrstice za polnjenje trenutne celice. Usmerite puščico v celico z največjo vrednostjo. Če so enaki, pokažite na katerega koli. Vnesite vrednosti
Korak 2 se ponavlja, dokler se tabela ne zapolni. Izpolnite vse vrednosti
Vrednost v zadnji vrstici in zadnjem stolpcu je dolžina najdaljšega skupnega zaporedja. Spodnji desni kot je dolžina LCS
Če želite najti najdaljšo skupno podsekvenco, začnite od zadnjega elementa in sledite smeri puščice. Elementi, ki ustrezajo simbolu (), tvorijo najdaljšo skupno podsekcijo. Ustvari pot po puščicah

Tako je najdaljša skupna podsekcija CD.

LCS

Kako je algoritem dinamičnega programiranja med reševanjem problema LCS učinkovitejši od rekurzivnega algoritma?

Metoda dinamičnega programiranja zmanjša število klicev funkcij. Shrani rezultat vsakega klica funkcije, tako da ga je mogoče uporabiti v prihodnjih klicih brez potrebe po odvečnih klicih.

V zgornjem dinamičnem algoritmu so rezultati, dobljeni z vsako primerjavo med elementi X in elementi Y, shranjeni v tabeli, da jih je mogoče uporabiti v prihodnjih izračunih.

Torej, čas, ki ga potrebuje dinamični pristop, je čas, potreben za izpolnitev tabele (tj. O (mn)). Medtem ko ima algoritem rekurzije zahtevnost 2 ^{max (m, n)} .

Najdaljši pogosti algoritem naslednjih sledi

 X in Y sta dve dani zaporedji Inicializirajte tabelo LCS dimenzije X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Start from LCS ( 1) (1) Primerjaj X (i) in Y (j) Če je X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Puščico usmerite na LCS (i) (j) Drugače LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Puščico usmerite na max (LCS (i-1) ( j), LCS (i) (j-1))

Primeri Python, Java in 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); )