最长公共子串

阳光穿透心脏的1/2处 2023-09-29 09:27 25阅读 0赞

#### 文章目录 ####

*   *   *  1. 最长公共子串
         *   *  描述
             *  解析
             *  代码

#### 1. 最长公共子串 ####

##### 描述 #####

有两个字符串（可能包含空格）,请找出其中最长的公共连续子串,输出其长度。(长度在1000以内)

例如：  
输入：abcde bcd  
输出：3

##### 解析 #####

1、把两个字符串分别以行和列组成一个二维矩阵。  
2、比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。  
3、通过查找出值为1的最长对角线就能找到最长公共子串。

比如：str=acbcbcef，str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串长度为5。

针对于上面的两个字符串我们可以得到的二维矩阵如下：

![在这里插入图片描述][b87618db6ee7430bbeb1cbd057b24c3e.png]  
从上图可以看到，str1 和 str2 共有 5 个公共子串，但最长的公共子串长度为 5。

为了进一步优化算法的效率，我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度，即某个二维矩阵元素的值由 record\[i\]\[j\]=1 演变为 record\[i\]\[j\]=1 +record\[i-1\]\[j-1\] ，这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下：  
![在这里插入图片描述][3200ca67a50f4bc5a0ec745d39873be7.png]  
递推公式为：  
当A\[i\] != B\[j\]，dp\[i\]\[j\] = 0  
当A\[i\] == B\[j\]，  
若i = 0 || j == 0，dp\[i\]\[j\] = 1  
否则 dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + 1

##### 代码 #####

> 仔细看看，一定可以掌握

**暴力法**

public int getLCS(String s, String s2) {
        
            if (s == null || t == null) {
        
                return 0;
            }
            int l1 = s.length();
            int l2 = t.length();
            int res = 0;
            for (int i = 0; i < l1; i++) {
        
                for (int j = 0; j < l2; j++) {
        
                    int m = i;
                    int k = j;
                    int len = 0;
                    while (m < l1 && k < l2 && s.charAt(m) == t.charAt(k)) {
        
                        len++;
                        m++;
                        k++;
                    }
                    res = Math.max(res, len);
                }
            }
            return res;
        }

**动态规划**

public int getLCS(String s, String t) {
        
            if (s == null || t == null) {
        
                return 0;
            }
            int result = 0;
            int sLength = s.length();
            int tLength = t.length();
            int[][] dp = new int[sLength][tLength];
            for (int i = 0; i < sLength; i++) {
        
                for (int k = 0; k < tLength; k++) {
        
                    if (s.charAt(i) == t.charAt(k)) {
        
                        if (i == 0 || k == 0) {
        
                            dp[i][k] = 1;
                        } else {
        
                            dp[i][k] = dp[i - 1][k - 1] + 1;
                        }
                        result = Math.max(dp[i][k], result);
                    } else {
        
                        dp[i][k] = 0;
                    }
                }
            }
            return result;
        }

**简化-优化**

简化一下递推公式：  
当A\[i\] != B\[j\]，dp\[i\]\[j\] = 0  
否则 dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + 1  
全部都归结为一个公式即可，二维数组默认值为0

public int getLCS(String s, String t) {
        
            if (s == null || t == null) {
        
                return 0;
            }
            int result = 0;
            int sLength = s.length();
            int tLength = t.length();
            int[][] dp = new int[sLength + 1][tLength + 1];
            for (int i = 1; i <= sLength; i++) {
        
                for (int k = 1; k <= tLength; k++) {
        
                    if (s.charAt(i - 1) == t.charAt(k - 1)) {
        
                        dp[i][k] = dp[i - 1][k - 1] + 1;
                        result = Math.max(dp[i][k], result);
                    }
                }
            }
    //        for (int i = 1; i <= sLength + 1; i++) {
        
    //            for (int k = 1; k <= tLength + 1; k++) {
        
    //                System.out.print(dp[i - 1][k - 1] + " ");
    //            }
    //            System.out.println();
    //        }
            return result;
        }

行、列都多一行，更适应公式。

![在这里插入图片描述][e7c0ec29e68441eca27a7a9020955c6e.png_pic_center]

[b87618db6ee7430bbeb1cbd057b24c3e.png]: https://img-blog.csdnimg.cn/b87618db6ee7430bbeb1cbd057b24c3e.png
[3200ca67a50f4bc5a0ec745d39873be7.png]: https://img-blog.csdnimg.cn/3200ca67a50f4bc5a0ec745d39873be7.png
[e7c0ec29e68441eca27a7a9020955c6e.png_pic_center]: https://img-blog.csdnimg.cn/e7c0ec29e68441eca27a7a9020955c6e.png?pic_center