JavaString算法找出两个字符串中共有的最大部分

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()`方法来查找它们的最大公共子字符串。最后，我们将结果打印到控制台上。

用IDEA用字符串操作找出两个字符串中最大子字符串,

可以使用动态规划（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 代码实现该算法：

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)。