用java编写一个程序,找出两个字符串中最长的公共子字符串。例如,对于字符串“ABCDXYZ”,“XYZABCD”,最长的公共子字符串是“ABCD”。
时间: 2024-02-22 08:55:21 浏览: 24
好的,这是一个比较常见的字符串问题,可以使用动态规划来解决。具体的做法是,定义一个二维数组dp,其中dp[i][j]表示以第一个字符串中第i个字符和第二个字符串中第j个字符结尾的最长公共子字符串的长度。然后遍历两个字符串的所有字符,如果字符相同,则更新dp[i][j]为dp[i-1][j-1]+1,否则dp[i][j]为0。最后找到dp数组中的最大值,即为最长公共子字符串的长度。然后再根据最长公共子字符串的长度,从其中任意一个字符串中截取即可得到最长公共子字符串。
以下是Java代码实现:
```
public static String longestCommonSubstring(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int[][] dp = new int[m+1][n+1];
int maxLength = 0;
int endIndex = 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;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endIndex = i - 1;
}
} else {
dp[i][j] = 0;
}
}
}
return s1.substring(endIndex-maxLength+1, endIndex+1);
}
```
调用方式为:
```
String s1 = "ABCDXYZ";
String s2 = "XYZABCD";
String result = longestCommonSubstring(s1, s2);
System.out.println(result); // 输出:ABCD
```
注意,以上代码的时间复杂度为O(mn),其中m和n分别为两个字符串的长度。如果需要优化时间复杂度,可以使用后缀数组或者哈希等算法。