题目:
给定两个字符串,求出它们之间最长的相同子字符串的长度。
/* * 公共子串需要连续,公共子序列不需要连续 * dp矩阵第一列dp[0...M-1][0],如果str1[i]==str2[0],令dp[i][0]=1,否则dp[i][0]=0; * dp矩阵第一行dp[0][0...N-1],如果str1[0]==str2[j],令dp[0][j]=1,否则dp[0][j]=0; * 其他位置从左到右,从上到下计算,dp矩阵有以下两种情况: * a.如果str1[i]!=str2[j],说明在必须把str1[i]和str2[j]当做公共子串的最后一个字符是不可能的,所以dp[i][j]=0; * b.如果str1[i]==str2[j],说明str1[i]和str2[j]可以作为公共子串的最后一个字符,dp[i][j]=dp[i-1][j-1]+1; * 生成dp矩阵后,遍历dp矩阵,可以找到最大值及其位置,从而得到最长公共子串。 * 因为公共子串是连续的,所以我们得到长度和结束位置后,可以通过substring函数获取最长公共子串 * * 因为公共子串是连续的,所以在生成dp矩阵的过程中我们只用到了左上方的数,所以可以压缩为空间复杂度为O(1)的算法。 * 每次计算一条斜线,并比较最长公共子串的长度,从第0行,chs2.length-1列开始,向左移动, * 思想类似于对角线打印矩阵 */
public class 最长公共子串问题 { public static int[][] getdp(char[] str1, char[] str2) { 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; } } for (int j = 1; j < str2.length; j++) { if (str1[0] == str2[j]) { dp[0][j] = 1; } } 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; } } } return dp; } public static String lcst1(String str1, String str2) { if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) { return ""; } char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); int[][] dp = getdp(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); } //获取最长公共子串的优化算法 public static String lcst2(String str1, String str2) { if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) { return ""; } char[] chs1 = str1.toCharArray(); char[] chs2 = str2.toCharArray(); int row = 0; // 斜线开始位置的行 int col = chs2.length - 1; // 斜线开始位置的列 int max = 0; // 记录最大长度 int end = 0; // 最大长度更新时,记录子串的结尾位置 while (row < chs1.length) { int i = row; int j = col; int len = 0; // 从(i,j)开始向右下方遍历 while (i < chs1.length && j < chs2.length) { if (chs1[i] != chs2[j]) { len = 0; } else { len++; } // 记录最大值,以及结束字符的位置 if (len > max) { end = i; max = len; } i++; j++; } if (col > 0) { // 斜线开始位置的列先向左移动 col--; } else { // 列移动到最左之后,行向下移动 row++; } } return str1.substring(end - max + 1, end + 1); } public static void main(String[] args) { String str1 = "ABC1234567DEFG"; String str2 = "HIJKL1234567MNOP"; System.out.println(lcst1(str1, str2)); System.out.println(lcst2(str1, str2)); } }