Bài toán xâu con chung dài nhất (Longest Common Substring) là bài toán tìm xâu con chung dài nhất giữa hai xâu cho trước.
Ví dụ, cho hai xâu “abcdxyz” và “xyzabcd”, ta có xâu con chung dài nhất là “abcd” với độ dài là 4.
Để giải quyết bài toán này, ta có thể sử dụng thuật toán Dynamic Programming. Cụ thể, ta sử dụng một bảng 2 chiều để lưu độ dài của xâu con chung tại mỗi vị trí của hai xâu cho trước. Sau đó, ta tìm độ dài lớn nhất trong bảng đó và trích xuất xâu con chung tại vị trí tương ứng.
Dưới đây là code minh họa cho bài toán này trong Java:
public class LongestCommonSubstring {
public static String findLCS(String str1, String str2) {
int m = str1.length();
int n = str2.length();
int[][] LCSuff = new int[m + 1][n + 1];
int length = 0;
int row = 0;
int col = 0;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
LCSuff[i][j] = 0;
} else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1;
if (LCSuff[i][j] > length) {
length = LCSuff[i][j];
row = i;
col = j;
}
} else {
LCSuff[i][j] = 0;
}
}
}
if (length == 0) {
return "";
}
StringBuilder sb = new StringBuilder();
while (LCSuff[row][col] != 0) {
sb.insert(0, str1.charAt(row - 1));
row--;
col--;
}
return sb.toString();
}
}
Đây là một ví dụ về cách tìm độ dài của xâu con chung dài nhất (Longest Common Substring) trong hai chuỗi s và t bằng cách sử dụng lập trình động (Dynamic Programming) trong Java:
public class LongestCommonSubstring {
public static int lcs(String s, String t) {
int n = s.length();
int m = t.length();
int[][] dp = new int[n + 1][m + 1];
int maxLength = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLength = Math.max(maxLength, dp[i][j]);
}
}
}
return maxLength;
}
public static void main(String[] args) {
String s = "ABCD";
String t = "BCDE";
System.out.println("Độ dài của xâu con chung dài nhất là: " + lcs(s, t)); // kết quả: 3 (vì chuỗi con chung dài nhất là "BCD")
}
}
Trong đó, dp[i][j] là độ dài của xâu con chung dài nhất của chuỗi s có độ dài i và chuỗi t có độ dài j. Chúng ta sử dụng một ma trận dp để lưu trữ độ dài của xâu con chung dài nhất tại mỗi bước tính toán. Nếu các ký tự tại vị trí i trong chuỗi s và j trong chuỗi t giống nhau, thì dp[i][j] được tính dựa trên dp[i-1][j-1] và tăng thêm 1. Đồng thời, chúng ta sử dụng biến maxLength để lưu trữ giá trị lớn nhất của dp[i][j] để tìm độ dài của xâu con chung dài nhất. Cuối cùng, kết quả là giá trị của maxLength.