Đang tải…
Đang tải…
Điền bảng với dp[i][j] là độ dài LCS của i và j ký tự đầu — mỗi ô suy ra từ ô chéo, trên hoặc trái.
Hàng & cột 0 = 0 (chuỗi rỗng không khớp gì).
1int lcs(String text1, String text2) {2 int len1 = text1.length(), len2 = text2.length();3 int[][] dp = new int[len1+1][len2+1]; // hàng/cột 0 = 04 for (int i = 1; i <= len1; i++)5 for (int j = 1; j <= len2; j++)6 if (text1.charAt(i-1) == text2.charAt(j-1)) // cùng ký tự?7 dp[i][j] = dp[i-1][j-1] + 1; // nối dài ô chéo + 18 else9 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); // lớn nhất của trên, trái10 return dp[len1][len2]; // độ dài LCS11}