Trình tự con chung dài nhất

Trong hướng dẫn này, bạn sẽ tìm hiểu cách tìm thấy dãy con chung dài nhất. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của dãy con chung dài nhất trong C, C ++, Java và Python.

Dãy con chung dài nhất (LCS) được định nghĩa là dãy con dài nhất chung cho tất cả các dãy đã cho, miễn là các phần tử của dãy con không bắt buộc phải chiếm các vị trí liên tiếp trong dãy ban đầu.

Nếu S1 và S2 là hai dãy đã cho thì Z là dãy con chung của S1 và S2 nếu Z là dãy con của cả S1 và S2. Hơn nữa, Z phải là một chuỗi tăng dần các chỉ số của cả S1 và S2.

Theo một trình tự tăng dần, chỉ số của các phần tử được chọn từ các trình tự ban đầu phải theo thứ tự tăng dần trong Z.

Nếu

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

Khi đó, (A, D, B)không thể là một dãy con của S1 vì thứ tự của các phần tử không giống nhau (tức là không phải là dãy tăng dần).

Hãy để chúng tôi hiểu về LCS bằng một ví dụ.

Nếu

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

Sau đó, các chuỗi con phổ biến là (B, C), (C, D, A, C), (D, A, C), (A, A, C), (A, C), (C, D), …

Trong số các (C, D, A, C)dãy con này , là dãy con chung dài nhất. Chúng ta sẽ tìm ra dãy con chung dài nhất này bằng cách sử dụng lập trình động.

Trước khi tiếp tục, nếu bạn chưa biết về lập trình động, vui lòng xem qua lập trình động.

Sử dụng Lập trình động để tìm LCS

Hãy để chúng tôi thực hiện hai chuỗi:

Dãy

thứ nhất Dãy thứ hai

Các bước sau được thực hiện để tìm dãy con chung dài nhất.

Tạo một bảng kích thước n+1*m+1trong đó n và m lần lượt là độ dài của X và Y. Hàng đầu tiên và cột đầu tiên được điền bằng các số không. Khởi tạo bảng
Điền vào mỗi ô của bảng bằng cách sử dụng logic sau.
Nếu ký tự tương ứng với hàng hiện tại và cột hiện tại khớp với nhau, thì hãy điền vào ô hiện tại bằng cách thêm một ký tự vào phần tử đường chéo. Trỏ mũi tên vào ô chéo.
Khác lấy giá trị lớn nhất từ cột trước và phần tử hàng trước đó để điền vào ô hiện tại. Trỏ mũi tên vào ô có giá trị lớn nhất. Nếu chúng bằng nhau, hãy chỉ vào bất kỳ trong số chúng. Điền các giá trị
Bước 2 được lặp lại cho đến khi bảng được lấp đầy. Điền vào tất cả các giá trị
Giá trị ở hàng cuối cùng và cột cuối cùng là độ dài của dãy con chung dài nhất. Góc dưới cùng bên phải là chiều dài của LCS
Để tìm dãy con chung dài nhất, hãy bắt đầu từ phần tử cuối cùng và làm theo hướng của mũi tên. Các phần tử tương ứng với ký hiệu () tạo thành dãy con chung dài nhất. Tạo đường dẫn theo các mũi tên

Do đó, dãy con chung dài nhất là CD.

LCS

Làm thế nào để một thuật toán lập trình động hiệu quả hơn thuật toán đệ quy trong khi giải quyết một vấn đề LCS?

Phương pháp lập trình động làm giảm số lần gọi hàm. Nó lưu trữ kết quả của mỗi lần gọi hàm để có thể sử dụng trong các cuộc gọi sau này mà không cần các lệnh gọi dư thừa.

Trong thuật toán động trên, các kết quả thu được từ mỗi phép so sánh giữa các phần tử của X và các phần tử của Y được lưu trữ trong một bảng để chúng có thể được sử dụng trong các tính toán sau này.

Vì vậy, thời gian thực hiện theo phương pháp tiếp cận động là thời gian cần thiết để điền vào bảng (tức là. O (mn)). Trong khi đó, thuật toán đệ quy có độ phức tạp là 2 ^{max (m, n)} .

Thuật toán dãy con phổ biến nhất

 X và Y là hai chuỗi đã cho Khởi tạo bảng LCS có thứ nguyên X.length * Y.length X.label = X Y.label = Y LCS (0) () = 0 LCS () (0) = 0 Bắt đầu từ LCS ( 1) (1) So sánh X (i) và Y (j) Nếu X (i) = Y (j) LCS (i) (j) = 1 + LCS (i-1, j-1) Trỏ mũi tên đến LCS (i) (j) Khác LCS (i) (j) = max (LCS (i-1) (j), LCS (i) (j-1)) Trỏ mũi tên đến max (LCS (i-1) ( j), LCS (i) (j-1))

Ví dụ về Python, Java và 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); )