用Java编写一个程序小明有两个字符串,他想找出其中最长的公共连续子串的长度,希望你能帮助他。例如,两个字符串分别为“abcde”和“abdge”,结果为2。
时间: 2023-05-18 20:06:47 浏览: 108
输入两个字符串,求它们最长公共字串的长度
5星 · 资源好评率100%
可以使用动态规划来解决这个问题。具体步骤如下:
1. 定义一个二维数组dp,其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长公共连续子串的长度。
2. 初始化dp数组,将第一行和第一列都设为0。
3. 遍历两个字符串,如果第一个字符串的第i个字符和第二个字符串的第j个字符相等,则dp[i][j] = dp[i-1][j-1] + 1,否则dp[i][j] = 0。
4. 在遍历过程中,记录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;
}
调用该方法,传入两个字符串即可得到最长公共连续子串的长度。
阅读全文