NỘI DUNG
Bài toán xâu con chung dài nhất
Xâu s1 có dộ dài m và s2 có độ dài n ( m,n là hai số tự nhiên; n,m<250). Biết rằng s1,s2 chỉ chứa các kí tự ‘A’…’Z’.
Yêu cầu: Hãy viết phương trình tìm xâu con chung dài nhất của xâu s1 và s2.
Dữ liệu vào: Nhập từ bàn phím 2 xâu s1 và s2.
Kết quả: Xuất ra màn hình xâu con chung của 2 xâ s1 và s2.
Thuật toán
Để tìm xâu con chung dài nhất của hai xâu s1 và s2, ta có thể sử dụng giải thuật Dynamic Programming.
Giả sử m là độ dài của xâu s1 và n là độ dài của xâu s2. Đặt L(i,j) là độ dài của xâu con chung dài nhất của s1[0..i-1] và s2[0..j-1] (trong đó s1[0..i-1] và s2[0..j-1] là các xâu con của s1 và s2 có độ dài i và j).
Ta có thể tính toán L(i,j) bằng cách sử dụng công thức sau đây:
- Nếu s1[i-1] = s2[j-1], thì L(i,j) = L(i-1,j-1) + 1
- Nếu s1[i-1] != s2[j-1], thì L(i,j) = max(L(i-1,j), L(i,j-1))
Khi đã tính được ma trận L, ta có thể truy vết ngược lại để xác định xâu con chung dài nhất của s1 và s2.
Độ phức tạp của giải thuật này là O(mn), với m và n là độ dài của s1 và s2.
Ví dụ về thuật toán
Giả sử ta có hai xâu s1 = “ABCBDAB” và s2 = “BDCABA”. Ta sẽ lập bảng tính toán theo giải thuật Dynamic Programming như sau:
B D C A B A
0 0 0 0 0 0 0
A 0 0 0 0 1 1 1
B 0 1 1 1 1 2 2
C 0 1 1 2 2 2 2
B 0 1 1 2 2 3 3
D 0 1 2 2 2 3 3
A 0 1 2 2 3 3 4
B 0 1 2 2 3 4 4
Các ô trong bảng này được tính theo công thức sau:
if 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])
Trong đó, L[i][j] là độ dài của xâu con chung dài nhất của hai xâu con s1[1..i] và s2[1..j]. Trong bảng trên, các giá trị được tô màu xanh lá cây đại diện cho độ dài của xâu con chung dài nhất của s1 và s2.
Sau khi tính toán xong bảng, ta sử dụng một phương thức gọi là “truy vết” (backtracking) để xác định xâu con chung dài nhất của s1 và s2. Cụ thể, ta bắt đầu từ ô L[m][n] (với m và n là độ dài của hai xâu s1 và s2), nếu s1[m-1] = s2[n-1] thì ta thêm kí tự đó vào xâu con chung và di chuyển đến ô L[m-1][n-1]. Nếu không, ta so sánh giá trị ở ô L[m-1][n] và L[m][n-1], và di chuyển đến ô có giá trị lớn hơn.
Kết quả của ví dụ này là xâu con chung dài nhất của s1 và s2 là “BDAB”, với độ dài là 4.
Cài đặt bài toán xâu con chung dài nhất với Python
def find_LCS(s1, s2):
m = len(s1)
n = len(s2)
L = [[0] * (n+1) for i in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if 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])
# Truy vết ngược lại để xác định xâu con chung dài nhất của s1 và s2.
result = ""
i = m
j = n
while i > 0 and j > 0:
if s1[i-1] == s2[j-1]:
result = s1[i-1] + result
i -= 1
j -= 1
elif L[i-1][j] > L[i][j-1]:
i -= 1
else:
j -= 1
return result
# Nhập vào 2 xâu s1 và s2
s1 = input("Nhập xâu s1: ")
s2 = input("Nhập xâu s2: ")
# Tìm xâu con chung dài nhất của s1 và s2
result = find_LCS(s1, s2)
# Xuất kết quả
print("Xâu con chung dài nhất của s1 và s2 là:", result)
Cài đặt bài toán xâu con chung dài nhất với C++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 250;
int L[MAXN+1][MAXN+1];
string find_LCS(string s1, string s2) {
int m = s1.length();
int n = s2.length();
memset(L, 0, sizeof(L));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (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]);
}
}
}
string result = "";
int i = m, j = n;
while (i > 0 && j > 0) {
if (s1[i-1] == s2[j-1]) {
result = s1[i-1] + result;
i--;
j--;
} else if (L[i-1][j] > L[i][j-1]) {
i--;
} else {
j--;
}
}
return result;
}
int main() {
string s1, s2;
cout << "Nhap xau s1: ";
getline(cin, s1);
cout << "Nhap xau s2: ";
getline(cin, s2);
string result = find_LCS(s1, s2);
cout << "Xau con chung dai nhat cua s1 va s2 la: " << result << endl;
return 0;
}
Đánh giá độ phức tạp của thuật toán
Độ phức tạp của thuật toán tìm xâu con chung dài nhất của hai xâu s1 và s2 bằng giải thuật Dynamic Programming là O(mn), trong đó m và n lần lượt là độ dài của hai xâu s1 và s2.
Thuật toán này sử dụng một bảng tính toán độ dài của xâu con chung dài nhất của s1 và s2, với mỗi ô trong bảng được tính toán dựa trên giá trị của các ô trước đó. Vì vậy, ta cần phải tính toán tất cả các ô trong bảng, mỗi ô tốn O(1) thời gian, do đó độ phức tạp của thuật toán là O(mn).
Tuy nhiên, độ phức tạp không phải là tất cả. Thuật toán này còn tốn O(mn) bộ nhớ để lưu trữ bảng tính toán độ dài của xâu con chung dài nhất. Vì vậy, nếu m và n quá lớn, thuật toán này có thể gặp vấn đề về bộ nhớ. Tuy nhiên, với m và n nhỏ hơn 250 như trong yêu cầu đề bài, độ phức tạp và sử dụng bộ nhớ của thuật toán là rất hợp lý.
Ngoài thuật toán Dynamic Programming, còn có 2 thuật toán khác để giải bài toán tìm xâu con chung dài nhất của hai xâu s1 và s2, đó là:
Thuật toán Longest Common Subsequence (LCS) sử dụng giải pháp quy hoạch động (Dynamic Programming).
Độ phức tạp của thuật toán LCS cũng là O(mn), tương tự như thuật toán Dynamic Programming. Tuy nhiên, cách thức tính toán khác với Dynamic Programming. LCS tìm độ dài của xâu con chung dài nhất của hai xâu s1 và s2 bằng cách tính toán một bảng L[i][j], trong đó L[i][j] là độ dài của LCS của xâu s1[1..i] và s2[1..j]. Với mỗi ô trong bảng, ta chỉ cần tính toán giá trị của các ô trước đó, do đó độ phức tạp của thuật toán là O(mn).
Thuật toán Xử lý xâu Boyer-Moore sử dụng giải pháp tham lam (Greedy)
Độ phức tạp của thuật toán Boyer-Moore là O(mn), tương tự như thuật toán Dynamic Programming và LCS. Tuy nhiên, Boyer-Moore không sử dụng giải pháp quy hoạch động. Thay vào đó, Boyer-Moore tìm xâu con chung dài nhất bằng cách duyệt từng kí tự của s1 và s2, và so sánh các xâu con bắt đầu từ các kí tự đó. Nếu một xâu con có thể tiếp tục mở rộng, thuật toán sẽ tiếp tục duyệt đến khi không thể mở rộng nữa. Độ phức tạp của thuật toán Boyer-Moore cũng là O(mn), nhưng thường nhanh hơn Dynamic Programming và LCS trong các trường hợp đặc biệt.
Tóm lại, các thuật toán tìm xâu con chung dài nhất của hai xâu s1 và s2 đều có độ phức tạp là O(mn), tuy nhiên mỗi thuật toán có cách tiếp cận khác nhau và phù hợp với từng trường hợp cụ thể.