小明有两个字符串,他想找出其中最长的公共连续子串的长度,希望你能java帮助他。例如,两个字符串分别为“abcde”和“abdge”,结果为2。
时间: 2023-05-30 09:03:16 浏览: 135
java实现求两个字符串最长公共子串的方法
5星 · 资源好评率100%
可以使用动态规划的思想来解决这个问题。
假设有两个字符串s1和s2,分别长度为m和n。我们定义一个二维数组dp,其中dp[i][j]表示以s1的第i个字符和s2的第j个字符结尾的最长公共连续子串的长度。
我们可以根据以下状态转移方程计算dp数组:
dp[i][j] = 0 (i=0或j=0)
dp[i][j] = dp[i-1][j-1] + 1 (s1[i]==s2[j])
dp[i][j] = 0 (s1[i]!=s2[j])
其中dp[i][j]的值只可能是0或者dp[i-1][j-1]+1或者0,因为最长公共连续子串必须以s1[i]和s2[j]结尾。
最终的答案就是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 maxLength = 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;
maxLength = Math.max(maxLength, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return maxLength;
}
调用该方法:
String s1 = "abcde";
String s2 = "abdge";
int maxLength = longestCommonSubstring(s1, s2);
System.out.println(maxLength); // 输出2
阅读全文