java取两个字符串的最大交集

Java取两个字符串的最大交集的算法可以通过动态规划（Dynamic Programming）来实现，其中最长公共子串（Longest Common Substring, LCS）就是该问题的一个特例。

以下是完整的攻略：

步骤1：定义状态

定义一个二维数组 dp[i][j]，表示字符串 a 的前 i 个字符和字符串 b 的前 j 个字符的最长公共子串长度。

状态转移方程：

if(a.charAt(i - 1) == b.charAt(j - 1)) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
    dp[i][j] = 0;
}

步骤2：初始化状态

将第一列和第一行的值都设置为 0，即：

for(int i = 0; i <= a.length(); i++) {
    dp[i][0] = 0;
}

for(int i = 0; i <= b.length(); i++) {
    dp[0][i] = 0;
}

步骤3：更新状态

使用状态转移方程，遍历二维数组，求出最长公共子串的长度。

int maxLen = 0;
int end = 0;

for(int i = 1; i <= a.length(); i++) {
    for(int j = 1; j <= b.length(); j++) {
        if(a.charAt(i - 1) == b.charAt(j - 1)) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
            if(dp[i][j] > maxLen) {
                maxLen = dp[i][j];
                end = i - 1;
            }
        } else {
            dp[i][j] = 0;
        }
    }
}

步骤4：输出结果

从字符串 a 中取出最长公共子串，即输出 a.substring(end - maxLen + 1, end + 1)。

示例说明

假设有两个字符串 a 和 b，分别为：

String a = "programming";
String b = "programme";

则运行完上述算法后，可得到最长公共子串为 program，输出结果为：

System.out.println(a.substring(end - maxLen + 1, end + 1));
// 输出结果为： program

再举一个例子，两个字符串 a 和 b 分别为：

String a = "ababc";
String b = "babc";

则最长公共子串为 babc，输出结果为：

System.out.println(a.substring(end - maxLen + 1, end + 1));
// 输出结果为： babc