LCS: dãy ký tự chung dài nhất và cách truy vết

“Chung dài nhất” có bắt buộc liên tiếp không?

Hai xâu A=ABCBDAB và B=BDCABA có một dãy chung là BCBA. Trong A, chọn B ở vị trí 1, C ở 2, B ở 3, A ở 5 nếu đánh số từ 0. Trong B, chọn B ở 0, C ở 2, B ở 4, A ở 5. Các vị trí mỗi xâu đều tăng, nhưng không cần nằm sát nhau.

Đây là subsequence, thường được gọi dãy con hoặc xâu con không liên tiếp trong tài liệu tiếng Việt. Một substring phải là đoạn liên tiếp và có công thức khác. Cùng chữ viết tắt LCS đôi khi gây nhầm giữa hai bài, nên hãy đọc định nghĩa trong đề và tên tiếng Anh nếu có.

Sắp xếp ký tự của hai xâu rồi tìm giao sẽ làm mất thứ tự, nên không giải bài này. Chẳng hạn AB và BA cùng có A,B nhưng LCS chỉ dài 1, không thể lấy cả hai ký tự theo cùng thứ tự trong hai xâu.

Trạng thái theo hai tiền tố

Đặt dp[i][j] là độ dài LCS của A[0:i] và B[0:j]. i,j là số ký tự đã xét, không phải chỉ số ký tự cuối. Vì vậy khi i,j dương, hai ký tự cuối cần so là A[i−1] và B[j−1]. Bảng có n+1 hàng, m+1 cột để chứa cả tiền tố rỗng.

Khi một phía rỗng, dãy chung duy nhất có độ dài 0. Đặt hàng 0 và cột 0 bằng 0. Cơ sở này cũng giúp các ô đầu bảng dùng cùng công thức mà không truy cập chỉ số âm.

Nếu chỉ dùng một chỉ số như “đã xét i ký tự A”, ta chưa biết đã dùng tới đâu trong B. Hai lịch sử cùng i nhưng đã đi tới các vị trí khác nhau của B có khả năng nối tiếp khác nhau, nên không thể gộp tùy ý vào một trạng thái một chiều.

Hai trường hợp ở ký tự cuối

Nếu A[i−1] bằng B[j−1], ta có thể ghép ký tự đó vào một LCS của hai tiền tố ngắn hơn, cho dp[i−1][j−1]+1. Trong bài độ dài LCS cơ bản, tồn tại một đáp án tối ưu dùng cặp ký tự cuối bằng nhau này, nên giá trị đó là công thức đủ.

Nếu hai ký tự khác nhau, chúng không thể cùng làm ký tự cuối khớp với nhau. Một lời giải tối ưu phải bỏ qua ký tự cuối của ít nhất một phía: lấy max(dp[i−1][j],dp[i][j−1]). Không cộng hai ô này vì chúng là các lựa chọn thay thế, không phải hai nhóm số cách đang cần cộng.

Duyệt i tăng, trong mỗi hàng j tăng để các ô trên, trái và chéo trên-trái đã có giá trị. Có thể tổ chức thứ tự khác nếu vẫn tôn trọng phụ thuộc, nhưng đừng đổi hướng rồi đọc phải các ô chưa được tính.

Bảng đầy đủ của ví dụ

Hàng ghi tiền tố của A theo ký tự mới thêm, cột ghi tiền tố của B. Ký hiệu ∅ đại diện tiền tố rỗng. Ô cuối góc phải bằng 4.

Ví dụ tại hàng C, cột C, hai ký tự bằng nhau nên lấy ô chéo có giá trị 1 rồi cộng 1 thành 2. Tại ô cuối, B khác A nên lấy max của ô trên 4 và ô trái 4; đáp án vẫn 4. Hai lựa chọn bằng nhau báo khả năng có nhiều đường truy vết hợp lệ, không phải lỗi thuật toán.

Truy vết một dãy cụ thể

Bắt đầu i=n,j=m. Nếu hai ký tự cuối bằng nhau, ghi ký tự đó rồi giảm cả i,j. Nếu khác nhau, đi tới ô trên hoặc trái giữ giá trị tối ưu. Code ưu tiên ô trên khi hai giá trị bằng nhau để có quy tắc ổn định. Dừng khi một chỉ số về 0 rồi đảo chuỗi đã ghi, vì quá trình đi từ cuối về đầu.

Với ví dụ, từ (7,6) đi lên (6,6), ghi A và đi chéo. Sau đó đi lên để ghép B, đi trái để ghép C, rồi ghép B. Thứ tự thu khi đi ngược là A,B,C,B; đảo lại cho BCBA. Một thuật toán phá hòa khác có thể trả BDAB, cũng dài 4 và vẫn đúng.

Không phải cứ hai ký tự bất kỳ bằng nhau là lấy ngay theo tham lam. Cần nhìn cấu trúc tối ưu của hai tiền tố hoặc hậu tố tương ứng. Quy tắc truy vết phía trên bám vào bảng DP đã chứng minh, chứ không ghép cặp bằng nhau đầu tiên rồi bỏ phần còn lại tùy ý.

Code C++ và Python

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string lcs(const string& a,const string& b){
    int n=a.size(),m=b.size();vector<vector<int>> d(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
        if(a[i-1]==b[j-1])d[i][j]=d[i-1][j-1]+1;
        else d[i][j]=max(d[i-1][j],d[i][j-1]);
    }
    string result;int i=n,j=m;
    while(i>0 && j>0){
        if(a[i-1]==b[j-1]){result+=a[i-1];--i;--j;}
        else if(d[i-1][j]>=d[i][j-1])--i;
        else --j;
    }
    reverse(result.begin(),result.end());return result;
}
int main(){
    string a="ABCBDAB",b="BDCABA",line;
    if(getline(cin,line)){a=line;if(!getline(cin,b))b="";}
    string answer=lcs(a,b);cout<<answer.size()<<'\n'<<answer<<'\n';
}

import sys

def lcs(a,b):
    n,m=len(a),len(b)
    d=[[0]*(m+1) for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,m+1):
            if a[i-1]==b[j-1]:
                d[i][j]=d[i-1][j-1]+1
            else:
                d[i][j]=max(d[i-1][j],d[i][j-1])
    i,j=n,m;result=[]
    while i and j:
        if a[i-1]==b[j-1]:
            result.append(a[i-1]);i-=1;j-=1
        elif d[i-1][j]>=d[i][j-1]:
            i-=1
        else:
            j-=1
    return ''.join(reversed(result))

if __name__=='__main__':
    lines=sys.stdin.read().splitlines()
    a,b=(lines+[''])[:2] if lines else ('ABCBDAB','BDCABA')
    answer=lcs(a,b);print(len(answer));print(answer)

Không nhập dữ liệu, chương trình in dòng 4 rồi dòng BCBA. Input riêng gồm hai dòng là hai xâu; một dòng rỗng vẫn là một xâu hợp lệ. Code đọc nguyên dòng nên khoảng trắng bên trong cũng là ký tự và có thể được chọn trong LCS. Trong ví dụ chạy chung hai ngôn ngữ, giới hạn dữ liệu là ASCII để C++ char và Python str cùng đơn vị ký tự.

Với tiếng Việt Unicode, C++ string trên UTF-8 đếm byte còn Python str đếm điểm mã, nên không được nhận kết quả tương đương chỉ vì hai bản đều chạy. Muốn mở rộng cần thống nhất cách tách ký tự hoặc đơn vị so sánh, kể cả xử lý dấu kết hợp nếu ứng dụng yêu cầu. Phần đó nằm ngoài hợp đồng ví dụ ASCII này.

Cả hai hàm trả một xâu đáp án. Chương trình in độ dài rồi xâu đó; với đáp án rỗng, dòng thứ hai rỗng. Nếu hệ thống chỉ yêu cầu độ dài hoặc chấm một hàm, điều chỉnh phần giao tiếp theo đề, giữ nguyên ý nghĩa trạng thái bên trong.

Độ phức tạp và giảm bộ nhớ

Có (n+1)(m+1) ô, mỗi ô thực hiện một so sánh ký tự và vài thao tác số nguyên, nên thời gian O(nm) khi hai độ dài dương; lưu toàn bảng O(nm). Truy vết đi giảm một hoặc cả hai chỉ số, cần O(n+m) bước và bộ nhớ chứa dãy kết quả.

Nếu chỉ hỏi độ dài, mỗi hàng phụ thuộc hàng trước và ô bên trái của hàng hiện tại, nên có thể giữ hai hàng để dùng O(min(n,m)) bộ nhớ sau khi chọn chiều nhỏ hơn làm cột. Nhưng hai hàng không giữ lại toàn đường truy vết theo cách code hiện tại. Muốn vừa ít bộ nhớ vừa khôi phục dãy, cần phương pháp khác, chẳng hạn chia để trị phù hợp; không chỉ xóa bảng rồi giữ nguyên vòng truy vết.

Đừng lưu cả một xâu đáp án trong mỗi ô rồi vẫn gọi bộ nhớ O(nm). Các xâu có thể dài tới min(n,m), cùng chi phí sao chép khi nối, làm cận thực tế lớn hơn. Tệp minh họa lưu số nguyên rồi khôi phục một lần ở cuối để tách hai việc này.

So với xâu chung liên tiếp dài nhất

Nếu bắt buộc liên tiếp, khi hai ký tự không bằng nhau, độ dài đoạn chung kết thúc tại cặp đó phải về 0, không lấy max ô trên/trái để nối qua chỗ đứt. Đáp án còn có thể nằm ở bất kỳ ô nào, thay vì chỉ đọc ô cuối theo trạng thái tiền tố LCS.

Ví dụ AXB và AB có LCS là AB dài 2, nhưng đoạn chung liên tiếp dài nhất chỉ dài 1. Dùng cặp này để kiểm rằng bạn đang giải đúng biến thể. Các bài “xâu chung của N xâu” đi kèm băm và tìm kiếm nhị phân có thể đang hỏi substring; không gắn cùng lời giải chỉ vì tiêu đề tiếng Việt gần giống.

Kiểm bằng liệt kê dãy con nhỏ

Khi tự kiểm tra trên hai xâu ngắn (độ dài ≤ 10), bạn có thể sinh mọi xâu con của hai xâu để tìm độ dài chung lớn nhất, đồng thời kiểm tra xâu truy vết thực sự là xâu con của cả hai chuỗi đầu vào và đạt đúng độ dài tối ưu (vì một cặp xâu có thể có nhiều LCS hợp lệ khác ngoài BCBA).

Các ca gồm hai xâu rỗng, một phía rỗng, ký tự lặp, thứ tự đảo, có khoảng trắng và xâu ngẫu nhiên. Hãy tự thử AA với A cho độ dài 1, AB với BA cho 1 và AXB với AB cho 2. Nếu code lấy cả số lần xuất hiện trong giao tần suất mà bỏ thứ tự, những ca này sẽ bộc lộ lỗi.

Luyện ngay trên Big-O Coding

Các bài dưới luyện LCS của hai chuỗi theo thứ tự. Trước khi nộp, kiểm đề hỏi độ dài hay cần khôi phục một dãy; nếu có nhiều đáp án, đọc quy tắc chọn hoặc cách chấm. Hãy giữ lại đối chứng vét cạn cho các xâu ngắn khi tối ưu bộ nhớ.

Câu hỏi thường gặp

Nguồn tham khảo

• Princeton: Longest Common Subsequence
• MIT: Dynamic programming lecture notes
• Python FAQ: multidimensional lists