最大公共子串java

最大公共子串（Longest Common Substring，简称LCS）是指两个字符串中最长的共有的连续子序列。在Java中，可以使用动态规划算法来解决这个问题。以下是基本步骤：

1. 定义一个二维数组`dp`，其中`dp[i][j]`表示字符串s1从0到i位置和字符串s2从0到j位置的最大公共子串长度。

2. 初始化`dp`数组：如果`s1[i]`等于`s2[j]`，则`dp[i][j] = dp[i-1][j-1] + 1`；否则，`dp[i][j] = 0`。

3. 遍历字符串s1和s2，更新dp数组。同时记录当前最长公共子串的结束位置`end`和长度`length`。

4. 当遍历结束后，`dp[m][n]`即为两个字符串的最大公共子串长度，其中`m`和`n`分别为两个字符串的长度。

5. 为了获取最长公共子串，可以从`dp[end][length]`开始回溯，找到原始字符串中的对应子串。

以下是简单的Java代码实现：

public class LCS {
    public String longestCommonSubsequence(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m+1][n+1];
        int end = 0;
        int length = 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] > length) {
                        length = dp[i][j];
                        end = i;
                    }
                } else {
                    dp[i][j] = 0;
                }
            }
        }

        return s1.substring(end - length, end);
    }
}