首页 > 代码库 > 一天一道算法题(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)---最长公共子串