Garākā kopējā seka

Šajā apmācībā jūs uzzināsiet, kā tiek atrasts garākais kopīgais rezultāts. Jūs atradīsit arī garākā kopīgā sekojuma C, C ++, Java un Python piemērus.

Garākā kopīgā sekvencija (LCS) ir definēta kā garākā sekvence, kas ir kopīga visām dotajām sekvencēm, ar nosacījumu, ka sekvences elementiem nav jāieņem secīgas pozīcijas sākotnējās sekvencēs.

Ja S1 un S2 ir divas norādītās secības, tad Z ir S1 un S2 kopīgā sekvence, ja Z ir gan S1, gan S2 sekvencija. Turklāt Z jābūt stingri pieaugošai S1 un S2 indeksu secībai .

Stingri pieaugošā secībā no sākotnējām secībām izvēlēto elementu indeksiem jābūt augošā secībā Z.

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

Tad (A, D, B)tas nevar būt S1 sekojums, jo elementu secība nav vienāda (ti, nav stingri palielināta secība).

Ļaujiet mums saprast LCS ar piemēru.

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

Tad bieži sastopamas sekvences ir (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Starp šīm sekām (C, D, A, C)ir garākā kopīgā seka. Mēs atradīsim šo garāko kopīgo seku, izmantojot dinamisko programmēšanu.

Pirms turpināt, ja vēl nezināt par dinamisko programmēšanu, lūdzu, veiciet dinamisko programmēšanu.

Dinamiskās programmēšanas izmantošana LCS atrašanai

Ņemsim divas secības:

Pirmā secība

Otrā secība

Lai atrastu garāko kopīgo seku, tiek veiktas šādas darbības.

Izveidojiet dimensiju tabulu, n+1*m+1kur n un m ir attiecīgi X un Y garumi. Pirmā rinda un pirmā kolonna ir aizpildītas ar nullēm. Inicializējiet tabulu
Aizpildiet katru tabulas šūnu, izmantojot šādu loģiku.
Ja rakstzīme, kas atbilst pašreizējai rindai un kolonnai, atbilst, aizpildiet pašreizējo šūnu, pievienojot vienu diagonālajam elementam. Norādiet bultiņu uz diagonālo šūnu.
Pārējais ņem maksimālo vērtību no iepriekšējās kolonnas un iepriekšējā rindas elementa, lai aizpildītu pašreizējo šūnu. Norādiet bultiņu uz šūnu ar maksimālo vērtību. Ja tie ir vienādi, norādiet uz kādu no tiem. Aizpildiet vērtības
2. darbību atkārto, līdz tabula ir aizpildīta. Aizpildiet visas vērtības
Pēdējās rindas un pēdējās kolonnas vērtība ir garākās kopējās sekcijas garums. Apakšējais labais stūris ir LCS garums
Lai atrastu garāko kopīgo seku, sāciet no pēdējā elementa un sekojiet bultiņas virzienam. Elementi, kas atbilst simbolam (), veido garāko kopīgo seku. Izveidojiet ceļu atbilstoši bultiņām

Tādējādi garākā kopīgā seka ir CD.

LCS

Kā dinamiskā programmēšanas algoritms ir efektīvāks par rekursīvo algoritmu, risinot LCS problēmu?

Dinamiskās programmēšanas metode samazina funkciju izsaukumu skaitu. Tajā tiek saglabāts katra funkcijas zvana rezultāts, lai to varētu izmantot turpmākajos zvanos bez liekiem zvaniem.

Iepriekš minētajā dinamiskajā algoritmā rezultāti, kas iegūti no katra X elementu un Y elementu salīdzinājuma, tiek saglabāti tabulā, lai tos varētu izmantot turpmākajos aprēķinos.

Tātad dinamiskās pieejas laiks ir laiks, kas vajadzīgs tabulas aizpildīšanai (ti, O (mn)). Rekursijas algoritma sarežģītība ir 2 ^{max (m, n)} .

Garākais kopīgo seku algoritms

 X un Y ir divas norādītās secības. Inicializējiet tabulas LCS ar izmēru X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Sākt no LCS ( 1) (1) Salīdziniet X (i) un Y (j) Ja X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Novietojiet bultiņu uz LCS (i) (j) Cita LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Norādiet bultiņu uz max (LCS (i-1) ( j), LCS (i) (j-1))

Python, Java un C / C ++ piemēri

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