Đâ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ụ[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
 ||
ABAA

Đị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 ${\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[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 ${\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ố[sửa | sửa mã nguồn]

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: ${\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":

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

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

Bài viết liên quan đến điện toán này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn. x t s