Tổng quan
Chuỗi Con Chung Dài Nhất tìm đoạn ký tự dài nhất xuất hiện liên tiếp trong cả hai chuỗi. Nó dùng đúng cái bảng của LCS với một quy tắc bị đổi, và chính thay đổi duy nhất đó là toàn bộ khác biệt giữa hai bài toán.
Ở LCS, một chỗ không khớp vẫn mang kết quả tốt nhất hiện có đi ngang: ô lấy giá trị lớn hơn trong hai ô kề. Ở đây không khớp thì ô về 0, vì chuỗi con không được phép có khoảng trống. Hệ quả là đáp án không còn nằm ở góc dưới phải — nó là giá trị lớn nhất ở bất kỳ đâu trong bảng, và bạn phải theo dõi nó ngay trong lúc điền.
Chuỗi Con Chung Dài Nhất hoạt động thế nào?
- Dựng bảng kích thước (m+1) × (n+1), trong đó hàng i và cột j đại diện cho các tiền tố của hai chuỗi, hàng 0 và cột 0 điền toàn số 0.
- Với mỗi cặp vị trí, so sánh hai ký tự tương ứng.
- Nếu khớp, đặt ô bằng ô chéo trên-trái cộng một — kéo dài đoạn vừa kết thúc ở cặp trước đó.
- Nếu không khớp, đặt ô về 0. Đoạn đã đứt và không có gì được mang sang.
- Theo dõi giá trị lớn nhất và vị trí của nó trong lúc điền; chuỗi con được đọc ngược từ vị trí đó với đúng số ký tự bằng giá trị ấy.
Khi nào nên dùng?
- Phát hiện đạo văn và trùng lặp, khi một đoạn giống nhau nguyên văn quan trọng hơn các từ chung rải rác.
- Tin sinh học — định vị một vùng liên tiếp được bảo tồn trong hai chuỗi DNA hoặc protein.
- So sánh tệp và mã hóa sai khác, khi khối giống nhau dài nhất là điểm neo để dựng một bản diff.
- Không phải công cụ đúng khi cho phép có khoảng trống — đó là bài Chuỗi Con Chung (LCS), và hai bài cho đáp án rất khác nhau.
Phân tích độ phức tạp
Thời gian là O(m·n): mỗi ô được tính đúng một lần với công việc hằng số. Bộ nhớ là O(m·n) cho bảng đầy đủ, nhưng nếu chỉ cần độ dài chứ không cần bản thân chuỗi con thì hai hàng là đủ và bộ nhớ giảm còn O(min(m, n)). Với đầu vào rất lớn, automaton hậu tố hoặc cây hậu tố tổng quát giải cùng bài toán trong thời gian tuyến tính, đổi lại cài đặt phức tạp hơn nhiều.
Câu hỏi thường gặp
Vì sao đáp án không nằm ở ô góc dưới phải như LCS?
Vì mỗi ô ở đây mang nghĩa 'độ dài đoạn chung kết thúc đúng tại cặp vị trí này', chứ không phải 'kết quả tốt nhất trên các tiền tố này'. Các đoạn kết thúc rải khắp bảng, nên giá trị lớn nhất có thể ở bất kỳ đâu và phải được theo dõi riêng.
Nếu có nhiều chuỗi con dài nhất bằng nhau thì sao?
Theo dõi một giá trị lớn nhất duy nhất sẽ trả về cái mà thứ tự điền chạm tới sau cùng. Muốn lấy hết, hãy ghi lại mọi vị trí có giá trị bằng cực đại rồi dựng lại từ từng vị trí đó.
Bản tối ưu hai hàng có còn dựng lại được chuỗi con không?
Có, miễn là bạn lưu thêm chỉ số kết thúc bên cạnh độ dài lớn nhất. Chuỗi con là một lát liên tiếp của chuỗi gốc, nên một vị trí kết thúc và một độ dài là đủ — khác với LCS, vốn cần cả bảng để lần ngược một đường đi.