Bài toán xâu con chung dài nhất

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Đây là bài toán tìm một xâu (string) hoặc nhiều xâu là xâu con của hai hoặc nhiều xâu. Không nên nhầm lẫn giữa bài toán này với Bài toán chuỗi con dài nhất.

Ví dụ[sửa | sửa mã nguồn]

Xâu con dài nhất của "ABAB", "BABA" và "ABBA" là các xâu "AB" và "BA" với độ dài bằng 2. Các xâu con khác (có độ dài ngắn hơn là "A" và "B").

 ABAB
  |||
  BABA
  ||
ABBA

Định nghĩa bài toán[sửa | sửa mã nguồn]

- Định nghĩa: Cho hai xâu S độ dài m và xâu T độ dài n, tìm xâu có độ dài lớn nhất là xâu con của cả hai xâu S và T. - Tổng quát hóa bài toán này là bài toán tìm xâu con k-chung (k-common substring problem): Cho một tập xâu S = \{S_1,..., S_K\}, trong đó |S_i|=n_i và Σn_i = N. Với mỗi giá trị k thỏa mãn 2 ≤ kK, tìm các xâu con chung dài nhất của ít nhất k xâu.

Thuật toán[sửa | sửa mã nguồn]

Có thể tìm độ dài và vị trí bắt đầu của các xâu con dài nhất của S và T trong \Theta(n+m) bằng cách sử dụng Cây hậu tố khái quát (Generalized suffix tree). Ngoài ra cũng có thể giải quyết bài toán theo phương pháp Quy hoạch động với độ phức tạp \Theta(nm).

Độ phức tạp của bài toán tổng quát tương ứng là \Theta(n_1 +... + n_K)\Theta(n_1·...·n_K).

Cây hậu tố[sửa | sửa mã nguồn]

Cây hậu tố tổng quát cho các xâu "ABAB", "BABA" và "ABBA", được đánh số tương ứng 0, 1 và 2.

Quy hoạch động[sửa | sửa mã nguồn]

Có thể tìm các hậu tố (suffix) dài nhất của các tiền tố (prefix) của các xâu. Hậu tố dài nhất được định nghĩa: 
\mathit{LCSuff}(S_{1..p}, T_{1..q}) = 
\begin{cases}
       \mathit{LCSuff}(S_{1..p-1}, T_{1..q-1}) + 1  & \mathrm{if} \; S[p] = T[q] \\
       0                                            & \mathrm{otherwise}
\end{cases}

Ví dụ với hai xâu "ABAB" và "BABA":

A B A B
0 0 0 0 0
B 0 0 1 0 1
A 0 1 0 2 0
B 0 0 2 0 3
A 0 1 0 3 0

Hậu tố dài nhất của các tiền tố có thể của các xâu ST chính là xâu con dài nhất của chúng. Các xâu con này được đánh dấu theo đường chéo, màu đỏ trong bảng. Ví dụ: các xâu con dài nhất là "BA" và "ABA": 
\mathit{LCSubstr}(S, T) = \max_{1 \leq i \leq m, 1 \leq j \leq n} \mathit{LCSuff}(S_{1..i}, T_{1..j}) \;

Có thể mở rộng phương pháp này để tìm xâu con dài nhất của nhiều xâu hơn nữa bằng cách đưa thêm 1 chiều vào bảng cho mỗi xâu mới.

Mã giả[sửa | sửa mã nguồn]

function LCSubstr(S[1..m], T[1..n])

    L:= array(0..m, 0..n)
    z:= 0
    ret:= {}
    for i:= 1..m
        for j:= 1..n
            if S[i] = T[j]
                if i = 1 or j = 1
                    L[i,j]:= 1
                else
                    L[i,j]:= L[i-1,j-1] + 1
                if L[i,j] > z
                    z:= L[i,j]
                    ret:= {}
                if L[i,j] = z
                    ret:= ret ∪ {S[i-z+1..i]}
    return ret

Thuật toán dùng quy hoạch động có độ phức tạp là O(m n).

Tham khảo[sửa | sửa mã nguồn]