Vừa bước chân vào trường THCS, Bé Bi đã đăng ký học đội tuyển học sinh giỏi tin học của nhà trường, và được tiếp xúc với một bài toán cơ bản là bài toán tìm xâu con chung dài nhất. Bài toán được phát biểu như sau:

Xâu ký tự T gọi là xâu con của xâu ký tự S nếu có thể xóa bớt một số ký tự trong xâu S để được xâu T (giữ nguyên thứ tự xuất hiện trong xâu S). Xâu ký tự C được gọi là xâu con chung dài nhất của xâu ký tự A và B nếu thỏa mãn:

• C là xâu con của xâu A;
• C là xâu con của xâu B;
• C có độ dài lớn nhất.

Sau khi làm xong bài toán trên, Bé Bi mới đặt một câu hỏi để mở rộng bài toán trên, đó là có bao nhiêu xâu khác nhau là xâu con chung dài nhất của xâu ký tự A và B? Biết rằng xâu X được gọi là khác xâu Y nếu tồn tại vị trị i sao cho X[i]≠Y[i].

Dữ liệu vào:

• Dòng đầu chứa xâu ký tự A;
• Dòng thứ hai chứa xâu ký tự B. Các xâu ký tự có độ dài không quá 500 ký tự và chỉ chứa chữ cái tiếng anh in thường.

Dữ liệu ra:

• Đưa ra hai số nguyên tương ứng là độ dài xâu con chung dài nhất và số lượng xâu con chung dài nhất khác nhau theo modul 666013?

Ví dụ:

Dữ liệu vào:

Dữ liệu ra:

Dữ liệu vào:

Dữ liệu ra:

Chú ý: Bài này chấm theo từng ý, trình chấm sẽ đọc hai số nguyên tương ứng với hai ý, mỗi ý đúng được $50% số điểm một test. (Bạn chỉ trả lời một ý cũng phải ghi ra hai số nguyên).

Xâu ký tự ~X~ được gọi là xâu con của xâu ký tự ~Y~ nếu ta có thể xoá đi một số ký tự trong xâu ~Y~ để được xâu ~X~.

Cho biết hai xâu ký tự ~A~ và ~B~ độ dài không quá ~2000~ ký tự, hãy tìm xâu ký tự ~C~ có độ dài lớn nhất và là con của cả ~A~ và ~B~.

Xâu ký tự ~X~ được gọi là xâu con của xâu ký tự ~Y~ nếu ta có thể xoá đi một số ký tự trong xâu ~Y~ để được xâu ~X~.

Cho biết hai xâu ký tự ~A~ và ~B~ chỉ gồm các chữ cái latin và chữ số, hãy tìm xâu ký tự ~C~ có độ dài lớn nhất và là con của cả ~A~ và ~B~.

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

include

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ể.