题目：
给定两个字符串 str1 和 str2，返回两个字符串的最长公共子串。
举例：
str1 = “1AB2345CD” str2 = “12345EF” 返回 “2345”
思路：
str1长度为M，str2长度为N，生成大小为M*N的矩阵dp ，dp[i][j]的含义是，在把str1[i] 和 str2[j] 当作公共子串最后一个字符的情况下，公共子串最长能有多长。
获取dp矩阵的代码如下：
public static int[][] getdp1(char[] str1, char[] str2) {
//初始化dp大小
int[][] dp = new int[str1.length][str2.length];
//初始化第一列
for (int i = 0;i < str1.length; i++) {
if (str1[i] == str2[0]){
dp[i][0] = 1;
} else {
dp[i][0] = 0;
}
}
//初始化第一行 第一个0位置已经初始化了，所以j从1开始
for (int j = 1;j < str1.length; j++) {
if (str1[0] == str2[j]){
dp[0][j] = 1;
} else {
dp[0][j] = 0;
}
}
//初始化其他位置
for (int i = 1; i < str1.length; i++) {
for (int j = 1; j < str2.length; j++) {
if (str1[i] == str2[j]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = 0;
}
}
}
return dp;
}测试结果：
通过得到的 dp 矩阵，可以知道 dp[3][4] 为最大值，那么最长公共子串的长度就是3，从 str[3] 开始向左一共 3 个字节的字符串 str[1..3]，就是最后要的最长公共字符串。
注意 subString函数，左闭右开。
找到最长公共子串代码如下：
public static String lcst(String str1, String str2) {
if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
return "";
}
char[] chs1 = str1.toCharArray();
char[] chs2 = str2.toCharArray();
int[][] dp = getdp1(chs1, chs2);
int end = 0;
int max = 0;
for (int i = 0; i < chs1.length; i++) {
for (int j = 0; j < chs2.length; j++) {
if (dp[i][j] > max) {
end = i;
max = dp[i][j];
}
}
}
return str1.substring(end - max + 1, end + 1);
}测试结果:
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/87952.html
