Pikim levinud tagajärg

Selles õpetuses saate teada, kuidas leitakse kõige pikem ühine järge. Samuti leiate toimivaid näiteid C, C ++, Java ja Pythoni kõige pikema levinud järjestuse kohta.

Pikim ühisjärjestus (LCS) on määratletud kui pikim järgnevus, mis on ühine kõikidele antud järjestustele, tingimusel et järgnevuse elementidel ei nõuta järjestikuste positsioonide hõivamist algsetes järjestustes.

Kui S1 ja S2 on kaks antud järjestust, siis on Z S1 ja S2 ühine alamjärjestus, kui Z on nii S1 kui ka S2 alamjärjestus. Lisaks peab Z olema nii S1 kui ka S2 indeksite rangelt kasvav järjestus .

Rangelt kasvavas järjestuses peavad algsete järjestuste hulgast valitud elementide indeksid olema kasvavas järjekorras Z-s.

Kui

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

Siis (A, D, B)ei saa see olla S1 järg, kuna elementide järjestus ei ole sama (st. Mitte järjest suurenev järjestus).

Mõistkem LCS-i ühe näitega.

Kui

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

Siis on tavalised järgnevused (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Nende järgnevuste hulgas (C, D, A, C)on pikim ühine järgnevus. Dünaamilise programmeerimise abil leiame selle pikima ühise järje.

Enne kui jätkate, kui te ei tea veel dünaamilisest programmeerimisest, läbige palun dünaamiline programmeerimine.

Dünaamilise programmeerimise kasutamine LCS leidmiseks

Võtame kaks järjestust:

Esimene järjestus

Teine järjestus

Pikima ühise järje leidmiseks järgitakse järgmisi samme.

Koostage mõõtude tabel, n+1*m+1kus n ja m on vastavalt X ja Y pikkused. Esimene rida ja esimene veerg on täis nullidega. Initsialiseeri tabel
Täitke iga tabeli lahter järgmise loogika abil.
Kui praegusele reale ja veerule vastavad koodid sobivad, täitke praegune lahter, lisades ühe diagonaalelemendile. Suunake nool diagonaalse lahtrisse.
Muul juhul võtke eelmise veeru ja eelmise reaelemendi maksimaalne väärtus praeguse lahtri täitmiseks. Suunake nool maksimaalse väärtusega lahtrile. Kui nad on võrdsed, osutage mõnele neist. Täitke väärtused
2. sammu korratakse, kuni tabel on täidetud. Täitke kõik väärtused
Viimase rea ja viimase veeru väärtus on kõige pikema ühise järje pikkus. Parempoolses alanurgas on LCS-i pikkus
Pikima ühise järje leidmiseks alustage viimasest elemendist ja järgige noole suunda. Sümbolile () vastavad elemendid moodustavad pikima ühise järje. Looge noolte järgi tee

Seega on pikim levinud järjend CD.

LCS

Kuidas on dünaamiline programmeerimisalgoritm efektiivsem kui rekursiivne algoritm LCS-i probleemi lahendamisel?

Dünaamilise programmeerimise meetod vähendab funktsioonikõnede arvu. See salvestab iga funktsioonikõne tulemuse, nii et seda saab tulevastes kõnedes kasutada ilma üleliigsete kõnede vajaduseta.

Ülaltoodud dünaamilises algoritmis salvestatakse X ja Y elementide igast võrdlusest saadud tulemused tabelisse, et neid saaks edaspidistes arvutustes kasutada.

Seega on dünaamilise lähenemise aeg tabeli täitmiseks kulunud aeg (st O (mn)). Rekursioonialgoritmi keerukus on 2 ^{max (m, n)} .

Pikim levinud tagajärgede algoritm

 X ja Y on kaks antud järjestust. Alustage tabeli LCS mõõtmetega X.pikkus * Y.pikkus X. silt = X Y. silt = Y LCS (0) () = 0 LCS () (0) = 0 Alusta LCS-ist ( 1) (1) Võrdle X (i) ja Y (j) Kui X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Suunake nool LCS-le (i) (j) Muu LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Suunake nool maksimumini (LCS (i-1) ( j), LCS (i) (j-1))

Pythoni, Java ja C / C ++ näited

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