Ilgiausias bendras pasekmė

Šioje pamokoje sužinosite, kaip randamas ilgiausias paplitęs tęsinys. Taip pat rasite ilgiausio įprasto sekos C, C ++, Java ir Python pavyzdžius.

Ilgiausias bendras seka (LCS) apibrėžiama kaip ilgiausia seka, kuri yra bendra visoms pateiktoms sekoms, su sąlyga, kad nereikalaujama, kad sekcijos elementai užimtų vienas po kito einančias pozicijas pirminėse sekose.

Jei S1 ir S2 yra dvi pateiktos sekos, tada Z yra bendra S1 ir S2 seka, jei Z yra tiek S1, tiek S2 seka. Be to, Z turi būti griežtai didėjanti S1 ir S2 indeksų seka .

Griežtai didėjančia seka elementų, pasirinktų iš pradinių sekų, indeksai turi būti didėjimo tvarka Z.

Jei

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

Tada (A, D, B)tai negali būti S1 seka, nes elementų tvarka nėra vienoda (t. Y. Griežtai nedidėja seka).

Supraskime LCS su pavyzdžiu.

Jei

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

Tada yra bendri padariniai (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Tarp šių pasekmių (C, D, A, C)yra ilgiausia paplitusi pasekmė. Mes rasime šį ilgiausią bendrą seką naudodami dinaminį programavimą.

Prieš tęsdami toliau, jei dar nežinote apie dinaminį programavimą, atlikite dinaminį programavimą.

Dinaminio programavimo naudojimas norint rasti LCS

Paimkime dvi sekas:

Pirmoji seka

Antroji seka

Norint rasti ilgiausią bendrą pasekmę, reikia atlikti šiuos veiksmus.

Sukurkite matmenų lentelę, n+1*m+1kur n ir m yra atitinkamai X ir Y ilgiai. Pirmoji eilutė ir pirmasis stulpelis užpildomi nuliais. Inicijuokite lentelę
Užpildykite kiekvieną lentelės langelį naudodami šią logiką.
Jei simbolis, atitinkantis dabartinę eilutę ir dabartinį stulpelį, sutampa, užpildykite esamą langelį, pridėdami vieną prie įstrižainės elemento. Nukreipkite rodyklę į įstrižainės langelį.
Kitur paimkite didžiausią vertę iš ankstesnio stulpelio ir ankstesnio eilutės elemento, kad užpildytumėte dabartinį langelį. Nukreipkite rodyklę į langelį, kurio vertė didžiausia. Jei jie yra lygūs, nurodykite bet kurį iš jų. Užpildykite reikšmes
2 veiksmas kartojamas, kol užpildoma lentelė. Užpildykite visas reikšmes
Paskutinės eilutės ir paskutinio stulpelio vertė yra ilgiausio bendro tęsinio ilgis. Apatiniame dešiniajame kampe yra LCS ilgis
Norėdami rasti ilgiausią bendrą eilę, pradėkite nuo paskutinio elemento ir vadovaukitės rodyklės kryptimi. Elementai, atitinkantys simbolį (), sudaro ilgiausią bendrą tęsinį. Sukurkite kelią pagal rodykles

Taigi ilgiausias paplitęs tęsinys yra CD.

LCS

Kaip dinaminis programavimo algoritmas yra efektyvesnis nei rekursinis algoritmas sprendžiant LCS problemą?

Dinaminio programavimo metodas sumažina funkcijų iškvietimų skaičių. Kiekvieno funkcijos skambučio rezultatas saugomas taip, kad jį būtų galima naudoti būsimuose skambučiuose nereikalaujant nereikalingų skambučių.

Aukščiau pateiktame dinaminiame algoritme rezultatai, gauti iš kiekvieno X elementų ir Y elementų palyginimo, yra saugomi lentelėje, kad juos būtų galima naudoti atliekant būsimus skaičiavimus.

Taigi dinamiško požiūrio laikas yra laikas, per kurį reikia užpildyti lentelę (ty O (mn)). Rekursijos algoritmo sudėtingumas yra 2 ^{max (m, n)} .

Ilgiausias bendro pasekmės algoritmas

 X ir Y yra dvi nurodytos sekos. Inicializuokite X matmens lentelę LCS. Ilgis * Y. ilgis X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Pradėti nuo LCS ( 1) (1) Palyginkite X (i) ir Y (j) Jei X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Nukreipkite rodyklę į LCS i) (j) Kita LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Nukreipkite rodyklę į maks. (LCS (i-1) ( j), LCS (i) (j-1))

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

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