Vấn đề chuỗi con chung dài nhất (LCS - Longest Common Subsequence) là một bài toán quan trọng trong việc tìm kiếm chuỗi con chung dài nhất cho một tập hợp các chuỗi. Khác với vấn đề về xâu con chung dài nhất, chuỗi con không cần phải chiếm các vị trí liên tiếp trong chuỗi ban đầu. Bài toán này có các ứng dụng rộng rãi trong ngôn ngữ học, tính toán và sinh học.
Để minh họa, hãy xem xét ví dụ với hai chuỗi (ABCD) và (ACBAD). Chúng có 5 chuỗi con chung với độ dài 2: (AB), (AC), (AD), (BD) và (CD); 2 chuỗi con chung với độ dài 3: (ABD) và (ACD); và không có chuỗi con chung nào khác có độ dài lớn hơn. Vì vậy, (ABD) và (ACD) là hai chuỗi con chung dài nhất của hai chuỗi ban đầu.
Độ phức tạp
Với trường hợp tổng quát có số lượng chuỗi đầu vào tùy ý, bài toán LCS là NP-khó. Tuy nhiên, khi số lượng chuỗi cố định, bài toán có thể giải được trong thời gian đa thức bằng cách sử dụng quy hoạch động.
Thuật toán cho hai chuỗi
Bài toán LCS có một cấu trúc con tối ưu, cho phép chia bài toán thành các bài toán con nhỏ hơn và dễ giải quyết hơn. LCS có các bài toán con chồng chéo, trong đó các bài toán con cấp cao sẽ sử dụng lại các nghiệm của các bài toán con cấp thấp hơn. Các thuộc tính này có thể được giải quyết bằng quy hoạch động, trong đó các giá trị tính toán được lưu lại để sử dụng sau này.
Tiền tố
Tiền tố của một chuỗi X được định nghĩa là chuỗi con chứa n ký tự đầu tiên của X. Ví dụ: các tiền tố của X = (AGCA) là X0 = (), X1 = (A), X2 = (AG), X3 = (AGC) và X4 = (AGCA).
Tính chất đầu tiên
LCS(X^A, Y^A) = LCS(X, Y)^A, cho tất cả các chuỗi X, Y và tất cả các ký hiệu A, trong đó dấu ^ biểu thị phép nối xâu. Điều này cho phép chúng ta đơn giản hóa việc tính toán LCS cho hai chuỗi kết thúc cùng một ký hiệu. Ví dụ: LCS("BANANA", "ATANA") = LCS("BANAN", "ATAN") ^ "A", LCS("BANANA", "ATANA") = LCS(" BAN "," AT ") ^" ANA".
Tính chất thứ hai
Nếu A và B là hai ký hiệu riêng biệt (A≠B), thì LCS(X^A, Y^B) là một trong hai xâu có độ dài cực đại trong tập {LCS(X^A, Y), LCS(X, Y^B)}, cho tất cả các xâu X và Y.
Ví dụ: LCS("ABCDEFG", "BCDGK") là xâu dài hơn của LCS("ABCDEFG", "BCDG") và LCS("ABCDEF", "BCDGK"); nếu cả hai có độ dài bằng nhau, ta có thể chọn tùy ý một trong những chuỗi thỏa mãn.
Định nghĩa hàm LCS
Cho hai chuỗi X = ( x1 x2 ⋯ xm ) và Y = ( y1 y2 ⋯ yn ). Các tiền tố của X là X1 , 2 , … , m ; tiền tố của Y là Y1 , 2 , … , n . Gọi LCS(Xi, Yj) là một hàm tính toán chuỗi con chung dài nhất cho Xi và Yj. Một hàm như vậy có hai tính chất đặc biệt như sau:
Tính chất đầu tiên
LCS(X^A, Y^A) = LCS(X, Y)^A, cho tất cả các chuỗi X, Y và tất cả các ký hiệu A, trong đó dấu ^ biểu thị phép nối xâu. Điều này cho phép chúng ta đơn giản hóa việc tính toán LCS cho hai chuỗi kết thúc cùng một ký hiệu. Ví dụ: LCS("BANANA", "ATANA") = LCS("BANAN", "ATAN") ^ "A", Tiếp tục cho các ký hiệu chung còn lại, LCS("BANANA", "ATANA") = LCS(" BAN "," AT ") ^" ANA".
Tính chất thứ hai
Nếu A và B là hai ký hiệu riêng biệt (A≠B), thì LCS(X^A, Y^B) là một trong hai xâu có độ dài cực đại trong tập {LCS(X^A, Y), LCS(X, Y^B)}, cho tất cả các xâu X và Y.
Ví dụ: LCS("ABCDEFG", "BCDGK") là xâu dài hơn của LCS("ABCDEFG", "BCDG") và LCS("ABCDEF", "BCDGK"); nếu cả hai có độ dài bằng nhau, ta có thể chọn tùy ý một trong những chuỗi thỏa mãn.
Mã cho giải pháp quy hoạch động
Dưới đây là một hàm để tính độ dài của LCS giữa hai chuỗi X và Y:
function LCSLength(X[1..m], Y[1..n])
C = array(0..m, 0..n)
for i:= 0..m
C[i, 0] = 0
for j:= 0..n
C[0, j] = 0
for i:= 1..m
for j:= 1..n
if X[i] = Y[j]
C[i, j] = C[i-1, j-1] + 1
else
C[i, j] = max(C[i, j-1], C[i-1, j])
return C[m, n]Qua ví dụ trên, ta đã tìm hiểu về bài toán chuỗi con chung dài nhất và cách giải quyết nó bằng thuật toán quy hoạch động. Bài toán này có ứng dụng rất lớn trong lĩnh vực khoa học máy tính và có thể được áp dụng trong nhiều lĩnh vực khác nhau.
Ảnh minh họa: So sánh hai bản sửa đổi của một tệp ví dụ, dựa trên dãy con chung dài nhất của chúng (màu đen)
