Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X.
Cho biết hai xâu ký tự A và B, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B.
Dòng 1: chứa xâu A
Dòng 2: chứa xâu B
Chỉ gồm một dòng ghi độ dài xâu C tìm được
Thuật toán
+ Gọi F[i,j] là độ dài xâu con chung dài nhất tìm được khi xét i kí tự đầu tiên trong A và j kí tự đầu tiên trong B.
+ Nếu A[i]=B[j] thì F[i,j]:=F[i-1,j-1]+1.
+ ngược lại F[i,j]:=max(F[i-1,j],F[i,j-1]).