用IDEA用字符串操作找出两个字符串中最大子字符串,
时间: 2024-03-16 12:42:29 浏览: 54
Java中对字符串进行加密和解密
5星 · 资源好评率100%
可以使用动态规划(DP)来解决这个问题。具体步骤如下:
1. 创建一个二维数组 dp,其中 dp[i][j] 表示第一个字符串前 i 个字符与第二个字符串前 j 个字符的最长公共子串的长度。
2. 初始化 dp 数组的第一行和第一列,都为0。
3. 遍历第一个字符串中的每个字符和第二个字符串中的每个字符,如果这两个字符相等,则 dp[i][j] = dp[i-1][j-1] + 1。
4. 如果这两个字符不相等,则 dp[i][j] = 0。
5. 在遍历的过程中,记录最长公共子串的长度和结束位置。
6. 最后根据结束位置和最长公共子串的长度可以得到最大子字符串。
下面是使用 Java 代码实现该算法:
``` java
public static String longestCommonSubstring(String str1, String str2) {
int m = str1.length();
int n = str2.length();
int[][] dp = new int[m+1][n+1];
int maxLength = 0;
int endPosition = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1.charAt(i-1) == str2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endPosition = i;
}
} else {
dp[i][j] = 0;
}
}
}
return str1.substring(endPosition - maxLength, endPosition);
}
```
以上代码时间复杂度为 O(mn),空间复杂度为 O(mn)。
阅读全文