Thuật toán Longest Common Subsequence (LCS) là một thuật toán động lập trình được sử dụng để tìm chuỗi con dài nhất chung của hai chuỗi. LCS là một bài toán phổ biến trong lĩnh vực xử lý ngôn ngữ tự nhiên, xử lý chuỗi và sinh tự động mã.
Để giải quyết bài toán LCS, ta sử dụng một bảng hai chiều để lưu trữ độ dài của các chuỗi con chung. Trong bảng này, hàng đầu tiên và cột đầu tiên được khởi tạo bằng 0. Sau đó, ta duyệt qua các ký tự của hai chuỗi và xây dựng bảng LCS dựa trên các giá trị của các ô liền trước của bảng.
Dưới đây là mã Java thực hiện thuật toán LCS:
public static String findLCS(String s1, String s2) {
int[][] lcs = new int[s1.length() + 1][s2.length() + 1];
for (int i = 0; i <= s1.length(); i++) {
for (int j = 0; j <= s2.length(); j++) {
if (i == 0 || j == 0) {
lcs[i][j] = 0;
} else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
lcs[i][j] = lcs[i - 1][j - 1] + 1;
} else {
lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
}
}
}
int index = lcs[s1.length()][s2.length()];
char[] lcsChars = new char[index];
int i = s1.length();
int j = s2.length();
while (i > 0 && j > 0) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
lcsChars[--index] = s1.charAt(i - 1);
i--;
j--;
} else if (lcs[i - 1][j] > lcs[i][j - 1]) {
i--;
} else {
j--;
}
}
return new String(lcsChars);
}
Trong đó, hàm findLCS nhận vào hai chuỗi s1 và s2 và trả về chuỗi con chung dài nhất giữa hai chuỗi đó. Thuật toán thực hiện việc xây dựng bảng lcs và sau đó lấy các ký tự của chuỗi con chung dài nhất từ bảng này.