Urutan Umum Terpanjang

Dalam tutorial ini, Anda akan mempelajari bagaimana urutan persekutuan terpanjang ditemukan. Selain itu, Anda akan menemukan contoh kerja dari urutan persekutuan terpanjang di C, C ++, Java dan Python.

Urutan umum terpanjang (LCS) didefinisikan sebagai urutan terpanjang yang umum untuk semua urutan yang diberikan, asalkan elemen urutan tidak diperlukan untuk menempati posisi berurutan dalam urutan asli.

Jika S1 dan S2 adalah dua urutan yang diberikan, maka Z adalah urutan dari S1 dan S2 jika Z adalah urutan dari S1 dan S2. Selanjutnya, Z harus merupakan urutan indeks S1 dan S2 yang meningkat secara ketat .

Dalam urutan yang semakin meningkat, indeks elemen yang dipilih dari urutan asli harus dalam urutan menaik di Z.

Jika

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

Kemudian, (A, D, B)tidak dapat menjadi urutan S1 karena urutan elemennya tidak sama (yaitu, urutan tidak meningkat secara ketat).

Mari kita pahami LCS dengan sebuah contoh.

Jika

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

Kemudian, urutan umum adalah (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Di antara (C, D, A, C)urutan berikut, adalah urutan umum terpanjang. Kita akan menemukan urutan umum terpanjang ini menggunakan pemrograman dinamis.

Sebelum melangkah lebih jauh, jika Anda belum mengetahui tentang pemrograman dinamis, silakan melalui pemrograman dinamis.

Menggunakan Pemrograman Dinamis untuk menemukan LCS

Mari kita ambil dua urutan:

Urutan pertama

Second Sequence

Langkah-langkah berikut diikuti untuk menemukan urutan persekutuan terpanjang.

Buat tabel dimensi di n+1*m+1mana n dan m adalah panjang masing-masing X dan Y. Baris pertama dan kolom pertama diisi dengan angka nol. Inisialisasi tabel
Isi setiap sel tabel menggunakan logika berikut.
Jika karakter yang sesuai dengan baris saat ini dan kolom saat ini cocok, maka isi sel saat ini dengan menambahkan satu ke elemen diagonal. Arahkan panah ke sel diagonal.
Lain mengambil nilai maksimum dari kolom sebelumnya dan elemen baris sebelumnya untuk mengisi sel saat ini. Arahkan panah ke sel dengan nilai maksimum. Jika mereka sama, tunjuk salah satu dari mereka. Isi nilainya
Langkah 2 diulangi sampai tabel terisi. Isi semua nilai
Nilai pada baris terakhir dan kolom terakhir adalah panjang deret persekutuan terpanjang. Sudut kanan bawah adalah panjang LCS
Untuk menemukan urutan persekutuan terpanjang, mulai dari elemen terakhir dan ikuti arah panah. Elemen yang sesuai dengan simbol () membentuk urutan persekutuan terpanjang. Buat jalur sesuai dengan panah

Jadi, urutan terpanjang adalah CD.

LCS

Bagaimana algoritma pemrograman dinamis lebih efisien daripada algoritma rekursif saat memecahkan masalah LCS?

Metode pemrograman dinamis mengurangi jumlah pemanggilan fungsi. Ini menyimpan hasil dari setiap panggilan fungsi sehingga dapat digunakan di panggilan selanjutnya tanpa perlu panggilan yang berlebihan.

Pada algoritma dinamik di atas, hasil yang diperoleh dari setiap perbandingan antara elemen X dan elemen Y disimpan dalam sebuah tabel sehingga dapat digunakan dalam perhitungan selanjutnya.

Jadi, waktu yang dibutuhkan oleh pendekatan dinamis adalah waktu yang dibutuhkan untuk mengisi tabel (mis. O (mn)). Sedangkan algoritma rekursi memiliki kompleksitas 2 ^{max (m, n)} .

Algoritma Urutan Umum Terpanjang

 X dan Y menjadi dua urutan yang diberikan Inisialisasi tabel LCS dimensi X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Mulai dari LCS ( 1) (1) Bandingkan X (i) dan Y (j) Jika X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Arahkan panah ke LCS (i) (j) Lain LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Arahkan panah ke max (LCS (i-1) ( j), LCS (i) (j-1))

Contoh Python, Java dan C / C ++

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