用java 编写一个程序:小明有两个字符串,他想找出其中最长的公共连续子串的长度,希望你能帮助他。例如,两个字符串分别为“abcde”和“abdge”,结果为2。
时间: 2023-05-18 08:06:34 浏览: 92
输入两个字符串,求它们最长公共字串的长度
5星 · 资源好评率100%
可以使用动态规划来解决这个问题。定义一个二维数组dp,其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长公共连续子串的长度。如果第一个字符串的第i个字符和第二个字符串的第j个字符相同,那么dp[i][j] = dp[i-1][j-1] + 1,否则dp[i][j] = 0。最后遍历整个dp数组,找到最大值即可。
以下是Java代码实现:
public static int longestCommonSubstring(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m+1][n+1];
int maxLen = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
maxLen = Math.max(maxLen, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return maxLen;
}
调用该方法,传入两个字符串即可得到最长公共连续子串的长度。例如:
String s1 = "abcde";
String s2 = "abdge";
int len = longestCommonSubstring(s1, s2);
System.out.println(len); // 输出2
阅读全文