用java 编写一个程序:小明有两个字符串,他想找出其中最长的公共连续子串的长度,希望你能帮助他。例如,两个字符串分别为“abcde”和“abdge”,结果为2。
时间: 2023-05-18 11:06:34 浏览: 49
可以使用动态规划来解决这个问题。定义一个二维数组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
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)