首页 > 代码库 > 一天一道算法题(5)---最长公共子串
一天一道算法题(5)---最长公共子串
-
题目
给定两个字符串str1和str2,返回两个字符串的最长公共子串。例如:str1="1AB2345CD",str2="12345EF",公共子串是“2345”
-
解析
最长公共子串和最长公共子序列的区别是,子串是连续的,子序列是不连续的。
首先还是要生成动态规划表。生成大小为M*N的矩阵dp。dp[i][j]的含义是,在必须把str1[i]和str2[j]当作公共子串最后一个字符的情况下,公共子串最长能有多长。比如,str1="A1234B",str2="CD1234",dp[3][4]的含义是在必须把str1[3]和str2[4]当作公共子串最后一个字符的情况下,公共子串能有多长。所以dp[3][4]=3。如果str1[i] != str2[j],那么dp[i][j]=0。具体求解过程如下:
1.矩阵dp第一列即dp[0..M-1][0]。如果str1[i]==str2[0],dp[i][0]=1,否则dp[i][0]=0。
2.矩阵dp第一行同上。
3.从左到右,从上到下可能有以下两种情况:
1)如果str1[i] != str2[j],那么dp[i][j]=0
2)如果str1[i] == str2[j],那么dp[i][j]=dp[i-1][j-1] + 1
计算dp矩阵的代码如下:
1 public int[][] getdp(char[] str1, char[] str2) { 2 int[][] dp = new int[str1.length][str2.length]; 3 for (int i = 0; i < str1.length; i++) { 4 if (str1[i] == str2[0]) 5 dp[i][0] = 1; 6 } 7 for (int j = 0; j < str2.length; j++) { 8 if (str1[0] == str2[j]) 9 dp[0][j] = 1; 10 } 11 for (int i = 1; i < str1.length; i++) { 12 for (int j = 1; j < str2.length; j++) { 13 if (str1[i] == str2[j]) { 14 dp[i][j] = dp[i-1][j-1] + 1; 15 } 16 } 17 } 18 return dp; 19 }
从dp矩阵中得到最长公共子串是非常容易的。只需要找到dp矩阵中最大的那个数即可。代码如下。
1 public String lcst1(String str1, String str2) { 2 if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) { 3 return ""; 4 } 5 char[] chs1 = str1.toCharArray(); 6 char[] chs2 = str2.toCharArray(); 7 int[][] dp = getdp(chs1, chs2); 8 int end = 0; 9 int max = 0; 10 for (int i = 0; i < chs1.length; i++) { 11 for (int j = 0; j < chs2.length; j++) { 12 if (dp[i][j] > max) { 13 end = i; 14 max = dp[i][j]; 15 } 16 } 17 } 18 return str1.substring(end-max+1, end+1); 19 }
上面的算法需要大小为M*N的矩阵,但实际上是可以减小到O(1)的,如下图所示,每一条斜线在计算之前生成整型变量len,len表示左上方位置的值,初始时len=0.从斜线最左上的位置开始向右下方依次计算每个位置的值。
代码实现如下:
1 public String lcst2(String str1, String str2) { 2 if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) { 3 return ""; 4 } 5 char[] chs1 = str1.toCharArray(); 6 char[] chs2 = str2.toCharArray(); 7 int row = 0; //斜线开始的行 8 int col = chs2.length - 1; //斜线开始的列 9 int max = 0; //记录最大长度 10 int end = 0; //最大长度更新时,记录子串的结尾位置 11 while (row < chs1.length) { 12 int i = row; 13 int j = col; 14 int len = 0; 15 //从(i, j)开始向右下方遍历 16 while (i < chs1.length && j < chs2.length) { 17 if (chs1[i] != chs2[j]) { 18 len = 0; 19 } else { 20 len++; 21 } 22 //记录最大值以及结束字符的位置 23 if (len > max) { 24 end = i; 25 max = len; 26 } 27 i++; 28 j++; 29 } 30 if (col > 0) { //斜线开始位置的列先向左移动 31 col--; 32 } else { //列移动到最左位置后,行向下移动 33 row++; 34 } 35 } 36 return str1.substring(end-max+1, end+1); 37 }
-
参考资料
《程序员代码面试指南》 左程云
一天一道算法题(5)---最长公共子串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。