Pengekalan Biasa Terpanjang

Dalam tutorial ini, anda akan mengetahui bagaimana penjelasan yang paling lama dijumpai. Anda juga akan dapati contoh-contoh kerja yang paling lama yang paling lama berlaku di C, C ++, Java dan Python.

Selanjutnya yang terpanjang (LCS) didefinisikan sebagai turutan terpanjang yang biasa bagi semua urutan yang diberikan, dengan syarat bahawa unsur-unsur yang berikutnya tidak diperlukan untuk menempati kedudukan berturut-turut dalam urutan asal.

Sekiranya S1 dan S2 adalah dua urutan yang diberikan maka, Z adalah turutan biasa S1 dan S2 jika Z adalah turutan kedua-dua S1 dan S2. Selanjutnya, Z mesti menjadi urutan peningkatan yang ketat bagi indeks S1 dan S2.

Dalam urutan yang semakin meningkat, indeks unsur-unsur yang dipilih dari urutan asal mestilah dalam urutan menaik dalam Z.

Sekiranya

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

Maka, (A, D, B)tidak boleh menjadi ikutan S1 kerana susunan elemen tidak sama (iaitu tidak meningkatkan urutan secara ketat).

Mari kita fahami LCS dengan contoh.

Sekiranya

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

Kemudian, perkara biasa adalah (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Di antara kesudahan ini, (C, D, A, C)adalah kesamaan yang terpanjang. Kami akan menemui kesamaan yang terpanjang ini menggunakan pengaturcaraan dinamik.

Sebelum melangkah lebih jauh, jika anda belum mengetahui tentang pengaturcaraan dinamik, silakan melalui pengaturcaraan dinamik.

Menggunakan Pengaturcaraan Dinamik untuk mencari LCS

Mari kita ambil dua urutan:

Urutan pertama Urutan

Kedua

Langkah-langkah berikut diikuti untuk mencari kesamaan yang paling lama.

Buat jadual dimensi n+1*m+1di mana n dan m masing-masing adalah panjang X dan Y. Baris pertama dan lajur pertama diisi dengan sifar. Permulaan jadual
Isi setiap sel jadual menggunakan logik berikut.
Sekiranya watak yang sesuai dengan baris semasa dan lajur semasa sepadan, isikan sel semasa dengan menambahkan satu ke elemen pepenjuru. Arahkan anak panah ke sel pepenjuru.
Jika tidak, ambil nilai maksimum dari elemen lajur dan baris sebelumnya untuk mengisi sel semasa. Arahkan anak panah ke sel dengan nilai maksimum. Sekiranya mereka sama, arahkan ke mana-mana. Isi nilai
Langkah 2 diulang sehingga meja diisi. Isi semua nilai
Nilai di baris terakhir dan lajur terakhir adalah panjang turutan sepanjang terpanjang. Sudut kanan bawah adalah panjang LCS
Untuk mencari kesamaan terpanjang, mulakan dari elemen terakhir dan ikuti arah anak panah. Unsur-unsur yang sesuai dengan () simbol membentuk turutan umum terpanjang. Buat jalan mengikut anak panah

Oleh itu, kesamaan yang paling lama adalah CD.

LCS

Bagaimana algoritma pengaturcaraan dinamik lebih efisien daripada algoritma rekursif semasa menyelesaikan masalah LCS?

Kaedah pengaturcaraan dinamik mengurangkan bilangan panggilan fungsi. Ini menyimpan hasil dari setiap panggilan fungsi sehingga dapat digunakan dalam panggilan masa depan tanpa memerlukan panggilan berlebihan.

Dalam algoritma dinamik di atas, hasil yang diperoleh dari setiap perbandingan antara elemen X dan elemen Y disimpan dalam jadual sehingga dapat digunakan dalam pengiraan masa depan.

Jadi, masa yang diambil oleh pendekatan dinamik adalah masa yang diambil untuk mengisi jadual (iaitu O (mn)). Manakala, algoritma rekursi mempunyai kerumitan 2 ^{maks (m, n)} .

Algoritma Pemulangan Biasa Terpanjang

 X dan Y menjadi dua urutan yang diberikan Memulakan jadual LCS dimensi X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Mula 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 anak panah ke LCS (i) (j) Lain LCS (i) (j) = maks (LCS (i-1) (j), LCS (i) (j-1)) Arahkan anak panah ke maksimum (LCS (i-1) ( j), LCS (i) (j-1))

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