描述

• 给定两个字符串str1和str2,输出两个字符串的最长公共子串
  题目保证str1和str2的最长公共子串存在且唯一。

方法一

思路

• 动态规划，字符串；

• 首先说明这里的公共子串是连续的，而不是可以不连续的子序列。

• 《算法导论》动态规划那一章详细介绍了最长公共子序列算法，参考该算法可以设计动态规划的方法求解最长公共子串。

• 对于两个字符串X=<x₁,x₂,……,x_m>与Y=<y₁,y₂,……,y_n>，定义X的第i前缀为X_i=<x₁,x₂,……,x_i>；

• 设Z=<z₁,z₂,……,z_k>是X和Y的最长公共子串，则存在如下三种情况：
  1.如果，则且Z_k-1是X_m-1和Y_n-1的一个最长公共子串；
  2.如果，则意味着Z是X_m-1和Y的一个最长公共子串；
  3.如果，则意味着Z是X和Y_n-1的一个最长公共子串。

• 即存在如下递推公式：
  若
  若。

• 故可创建二维dp数组，依据上述递推公式进行计算，。

• 参考下图示例：
  X = "1AB2345CD"，Y = "12345EF"
  

• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // 创建dp数组
        int[][] dp = new int[str1.length()][str2.length()];
        // 最长公共子串长度
        int max = 0;
        // 最长公共子串在str1与str2中的位置
        int row = 0;
        int col = 0;
        // 初始化边界
        for (int i = 0;i < str1.length();++i){
            if(str1.charAt(i) == str2.charAt(0))
                dp[i][0] = 1;
        }
        for (int i = 0;i < str2.length();++i){
            if(str1.charAt(0) == str2.charAt(i))
                dp[0][i] = 1;
        }
  
        // 填充dp数组，寻找最长公共子串
        for (int i = 1;i < str1.length();++i){
            for (int j = 1;j < str2.length();++j){
                if (str1.charAt(i) == str2.charAt(j)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    // 更新最长公共子串的信息
                    if (max < dp[i][j]){
                        row = i;
                        col = j;
                        max = dp[i][j];
                    }
                }
            }
        }
        return str1.substring(row+1-max,row+1);
    }
  }

• 时间复杂度：，双重循环，遍历字符串str1与str2；

• 空间复杂度：，使用二维dp数组辅助运算。

方法二

思路

• 方法一采用二维数组辅助计算，可以将其缩减为一维数组，从而降低程序空间消耗。

• 注意方法一的示例，计算dp二维数组的某个位置值时，其只与其左上角的数据有关，当然从公式也可以看出来。

  （1）

• 所以我们可以将二维dp数组压缩成一维dp数组，当然循环还是二重，外层循环从字符串X的0位置开始往右遍历，而对与字符串Y在从右往左遍历，这样外层循环每一次都是求二维dp数组第i行的所有值，至于内层循环从右往左遍历是为了避免覆盖之前求的值，譬如说，现在求第i行的所有数据，那么一维dp数组中存储的就是第i-1行的数据，若是内层循环从左往右进行，由公式（1）知道当前循环会直接覆盖之前求的值，无法进行正确公式（1）的运算。

• 代码如下：

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        int[] dp = new int[str2.length()+1];
        int max = 0;
        int row = 0;

        // 填充dp数组，寻找最长公共子串
        for (int i = 0;i < str1.length();++i){
            for (int j = str2.length() - 1;j >= 0;--j){
                // 两个字符相等
                if (str1.charAt(i) == str2.charAt(j)){
                    dp[j + 1] = dp[j] + 1;
                    if (max < dp[j + 1]){
                        row = i;
                        max = dp[j + 1];
                    }
                }else{
                    // 不相等
                    dp[j + 1] = 0;
                }
            }
        }
        return str1.substring(row - max + 1,row + 1);
    }
}

• 时间复杂度：，双重循环，遍历字符串str1与str2；
• 空间复杂度：，一维数组。