Đang tải…
Đang tải…
Cùng bảng với LCS nhưng đổi một quy tắc: không khớp thì ô về 0, vì chuỗi con phải liên tiếp.
Hàng và cột viền bằng 0: một tiền tố rỗng không chia sẻ chuỗi con nào với bất cứ gì.
1int longestCommonSubstring(String a, String b) {2 int m = a.length(), n = b.length(), best = 0;3 int[][] dp = new int[m + 1][n + 1];4 for (int i = 1; i <= m; i++)5 for (int j = 1; j <= n; j++)6 if (a.charAt(i-1) == b.charAt(j-1)) {7 dp[i][j] = dp[i-1][j-1] + 1;8 best = Math.max(best, dp[i][j]);9 } else dp[i][j] = 0; // về 0 — chuỗi con không thể bỏ qua ký tự10 return best;11}