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

Đâ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 chung dài nhất.

Ví dụ

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
 ||
ABAA

Định nghĩa bài toá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 ${\displaystyle S=\{S_{1},...,S_{K}\}}$, trong đó ${\displaystyle |S_{i}|=n_{i}}$ và Σ${\displaystyle n_{i}=N}$. Với mỗi giá trị k thỏa mãn 2 ≤ ${\displaystyle k}$ ≤ ${\displaystyle K}$, tìm các xâu con chung dài nhất của ít nhất ${\displaystyle k}$ xâu.

Thuật toá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 ${\displaystyle \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 ${\displaystyle \Theta (nm)}$.

Độ phức tạp của bài toán tổng quát tương ứng là ${\displaystyle \Theta (n_{1}+...+n_{K})}$ và ${\displaystyle \Theta (n_{1}}$·...·${\displaystyle n_{K})}$.

Cây hậu tố

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

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: ${\displaystyle {\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 S và T 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à "BAB" và "ABA": ${\displaystyle {\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ả

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à ${\displaystyle O(mn)}$.

Tham khảo