[动态规划][公共子串]最长公共子串、最长公共子序列

约定不等于承诺〃 2024-04-18 17:10 70阅读 0赞

# 1、最长公共子串 #

LintCode：[https://www.lintcode.com/problem/longest-common-substring/description][https_www.lintcode.com_problem_longest-common-substring_description]  
**题目描述**：最长公共子串  
给出两个字符串，找到最长公共子串，并返回其长度。

**样例**  
样例 1:  
输入: “ABCD” and “CBCE”  
输出: 2

解释:  
最长公共子串是 “BC”

样例 2:  
输入: “ABCD” and “EACB”  
输出: 1

解释:  
最长公共子串是 ‘A’ 或 ‘C’ 或 ‘B’

**简要分析**：按照动态规划的思路，设`f[i][j]`表示`A`字符串的前`i`个字符 与 `B`字符串的前`j`个字符中最长公共子串。那么在求解`f[i][j]`时，与`f[i - 1][j - 1]`密切相关，如果第`i`个字符与第`j`个字符相等，那么只需要在`f[i - 1][j - 1]`累加该值即可。如果第`i`个字符与第`j`个字符不想等，那么公共子串从此处断掉，`f[i][j] = 0`。

也可以通过用类似二维表格来理解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvb25na2luZ3doYXQ_size_16_color_FFFFFF_t_70]

**代码**：

public class Solution {
        /**
         * @param A: A string
         * @param B: A string
         * @return: the length of the longest common substring.
         */
        public int longestCommonSubstring(String A, String B) {
            // write your code here
            if(A == null || A.length() == 0 || B == null || B.length() ==0)
                return 0;
            int[][] f = new int[A.length()][B.length()]; //f[i][j]表示A字符串中前i个，与B字符串中前j个的最长公共子串长度
            
            for(int i = 0; i < A.length(); i ++){
                for( int j = 0; j < B.length(); j ++){
                    if(A.charAt(i) == B.charAt(j))
                        f[i][j] =  (i - 1 >= 0 && j - 1 >= 0) ? f[i - 1][j - 1] + 1 : 1;
                }
            }
            //遍历二维数组，寻找其中的最大值
            int maxRes = 0;
            for(int i = 0; i < A.length(); i ++){
                for( int j = 0; j < B.length(); j ++){
                    if(f[i][j] > maxRes)
                        maxRes = f[i][j];
                }
            }
            return maxRes;
        }
    }

# 2、最长公共子序列 #

**LintCode**：[https://www.lintcode.com/problem/longest-common-subsequence/description][https_www.lintcode.com_problem_longest-common-subsequence_description]

**题目描述**：最长公共子序列

最长公共子序列问题是在一组序列（通常2个）中找到最长公共子序列（注意：不同于子串，LCS不需要是连续的子串）。该问题是典型的计算机科学问题，是文件差异比较程序的基础，在生物信息学中也有所应用。

给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

**样例**  
样例 1:  
输入: “ABCD” and “EDCA”  
输出: 1

解释:  
LCS 是 ‘A’ 或 ‘D’ 或 ‘C’

样例 2:  
输入: “ABCD” and “EACB”  
输出: 2

解释:  
LCS 是 “AC”

**简要分析**：与公共子串不一样，子序列是可以不连续的。那么`f[i][j]`不仅仅是和`f[i - 1][j - 1]`存在依赖关系，其同时与`f[i - 1][j]`和`f[i][j - 1]`有关系。

如果A字符串中的第`i`个字符与B字符串中的第`j`个字符相等，可以直接在`f[i - 1][j - 1]`上累加。如果不相等，公共子串会直接断掉而`f[i][j] = 0`,子序列可以不连续，所以不需要赋值为`0`，只需要在当前范围的子范围内找到最大的子序列长度即可，即`Math.max(f[i - 1][j],f[i][j - 1])`.

**代码**：

public class Solution {
        /**
         * @param A: A string
         * @param B: A string
         * @return: The length of longest common subsequence of A and B
         */
        public int longestCommonSubsequence(String A, String B) {
            // write your code here
            if(A == null || A.length() == 0 || B == null || B.length() ==0 )
                return 0;
            int[][] f = new int[A.length() + 1][B.length() + 1];  //f[i][j]表示在A中到i字符串 与 B中到j位置的字符串中公共子序列的最大长度
            for(int i = 1; i <= A.length(); i ++){
                for(int j = 1; j <= B.length(); j ++){
                    if(A.charAt(i - 1) == B.charAt(j - 1))
                        f[i][j]  = f[i - 1][j - 1] + 1;
                    else
                        f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }
            }
    
            return f[A.length()][B.length()];
        }
    }

[https_www.lintcode.com_problem_longest-common-substring_description]: https://www.lintcode.com/problem/longest-common-substring/description
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvb25na2luZ3doYXQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/25ac02e1e67e4e25aad70a8008a8d7da.png
[https_www.lintcode.com_problem_longest-common-subsequence_description]: https://www.lintcode.com/problem/longest-common-subsequence/description