JavaString算法找出两个字符串中共有的最大部分
时间: 2024-05-25 21:16:04 浏览: 15
1. 暴力枚举法
- 遍历第一个字符串的所有子串。
- 判断子串是否在第二个字符串中出现,如果出现并且长度大于当前最大长度,则更新最大长度。
- 返回最大长度。
时间复杂度:O(n^3)
2. 动态规划法
- 定义一个二维数组dp,dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符为结尾的最大公共子串长度。
- 如果第一个字符串的第i个字符和第二个字符串的第j个字符相同,则dp[i][j] = dp[i-1][j-1] + 1。
- 如果第一个字符串的第i个字符和第二个字符串的第j个字符不同,则dp[i][j] = 0。
- 在求解过程中,记录最大的dp[i][j],即为最大公共子串的长度。
时间复杂度:O(n^2)
3. 后缀数组法
- 将两个字符串拼接起来,并在相邻字符串之间插入一个不在两个字符串中出现的字符,如$。
- 构建后缀数组。
- 遍历后缀数组,求解相邻两个后缀的最长公共前缀长度,取最大值即为两个字符串的最大公共部分长度。
时间复杂度:O(nlogn)
相关问题
Java代码实现String算法找出两个字符串中共有的最大部分
以下是Java代码实现:
```
public class CommonSubstring {
public static String findCommonSubstring(String str1, String str2) {
int m = str1.length();
int n = str2.length();
int[][] L = new int[m + 1][n + 1];
int len = 0, row = 0, col = 0;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
L[i][j] = 0;
} else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
L[i][j] = L[i - 1][j - 1] + 1;
if (L[i][j] > len) {
len = L[i][j];
row = i;
col = j;
}
} else {
L[i][j] = 0;
}
}
}
if (len == 0) {
return "";
}
StringBuilder sb = new StringBuilder();
while (L[row][col] != 0) {
sb.insert(0, str1.charAt(row - 1));
row--;
col--;
}
return sb.toString();
}
public static void main(String[] args) {
String str1 = "abcdefg";
String str2 = "defghijk";
System.out.println("Two strings: " + str1 + ", " + str2);
System.out.println("Common substring: " + findCommonSubstring(str1, str2));
}
}
```
在这个示例中,我们首先定义了一个名为`findCommonSubstring()`的静态方法,它接收两个字符串`str1`和`str2`作为参数。我们使用一个二维数组`L`来存储计算出的最大公共子字符串的长度,并使用三个变量`len`、`row`和`col`来跟踪最大公共子字符串的长度、行索引和列索引。我们使用两个嵌套的for循环来计算`L`数组中的所有元素。如果当前字符匹配,则将`L[i][j]`设置为`L[i-1][j-1]+1`,并检查是否需要更新`len`、`row`和`col`。如果两个字符不匹配,则将`L[i][j]`设置为0。最后,我们检查`len`是否为0,如果是,则返回一个空字符串,否则将最大公共子字符串添加到一个StringBuilder对象中,并返回它的字符串表示形式。
在`main()`方法中,我们定义了两个字符串`str1`和`str2`,并调用`findCommonSubstring()`方法来查找它们的最大公共子字符串。最后,我们将结果打印到控制台上。
Java找出两个字符串中所有共同的子串。
您好!关于您的问题,要找出两个字符串中所有共同的子串,可以采用暴力匹配法,对于其中一个字符串,逐个截取所有长度相同的子串,然后在另一个字符串中查找是否存在相同的子串,找到则记录下来即可。
代码示例:
```java
public static List<String> findCommonSubstrings(String s1, String s2) {
List<String> commonSubstrings = new ArrayList<>();
for (int i = 0; i < s1.length(); i++) {
for (int j = i + 1; j <= s1.length(); j++) {
String substring = s1.substring(i, j);
if (s2.indexOf(substring) != -1) {
commonSubstrings.add(substring);
}
}
}
return commonSubstrings;
}
```
注意,以上仅为一种常见的解法,实际上还存在更高效的算法,例如动态规划和后缀树等。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)