Chuỗi Chung Ngắn Nhất

Chuỗi chung ngắn nhất (SCS) của hai chuỗi X và Y là chuỗi ngắn nhất chứa X và Y như là chuỗi con.

Nói đơn giản, là cho hai chuỗi str1 và str2, hãy tìm chuỗi ngắn nhất chứa cả hai chuỗi str1 và str2.

Bài toán này có liên quan chặc chẽ với tìm chuỗi con chung dài nhất (LCS).

Ví dụ

Input:   str1 = "geek",  str2 = "eke"
Output: "geeke"
Input:   str1 = "AGGTAB",  str2 = "GXTXAYB"
Output:  "AGXGTXAYB"