最长公共子串

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串。题目保证str1和str2的最长公共子串存在且唯一。 
示例
输入："1AB2345CD","12345EF"
返回值："2345"

方法一

思路分析

本题方法一直接通过暴力法，寻找最长公共子串，双循环字符串str1的开始位置出发与另一个字符串str2比较，记录当下位置的最长公共子串，然后移动str1到下一位置，找到当前位置下的最长公共子串，直到遍历完str1的所有字符。

核心代码 

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // write code here
        int len1=str1.size();
        int len2=str2.size();
        if(len1==0||len2==0) return 0;
        int max_lcs=0;//设置当前最长公共字串长度0
        int start_i=0;
        for(int i=0;i<len1;i++)
        {
            for(int j=0;j<len2;j++)//每次str2从头开始遍历寻找最大公共子串
            {
                int index_i=i;
                int index_j=j;
                int current_lcs=0;//当前位置下的最长公共子串
                while(index_i<len1&&index_j<len2&&str1[index_i]==str2[index_j])
                {
                    index_i++;
                    index_j++;
                    current_lcs++;//当前位置下的最长公共子串加1
                }
                if(max_lcs<current_lcs)//更新最长公共子串
                {
                    max_lcs=current_lcs;
                    start_i=i;
                }
                
            }
            
        }
        return str1.substr(start_i,max_lcs);
        
        
    }
};
复杂度分析
  • 时间复杂度：暴力求解算法时间复杂度为$O(len(str1)*len(str2))$
  • 空间复杂度：时间复杂度为$O(1)$

方法二

思路分析

本题需要使用动态规划的办法。方法一中每次比较并没有记录有用的信息，因此使用一个二维数组存储有用的信息，$dp[i][j]$表示以str1[i-1]和str2[i-1]为公共子串最后一个字符的公共子串长度，那么如果这两个字符相等，则$dp[i][j]=dp[i-1][j-1]+1$，否则为0，因此很容易得到转移方程：
dp[i][j]=\left\{ <br /> \begin{array}{**lr**} <br /> 0, & i=0/j=0 \\ <br /> dp[i-1][j-1]+1, & str1[i-1]=str2[j-1]\\ <br /> 0, & str1[i-1] !=str2[j-1] <br /> \end{array} <br />\right.
根据得到的子串长度以及最后一个字符相等的位置输出最长公共子串。

图解


核心代码 

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // write code here
        int len1=str1.size();
        int len2=str2.size();
        if(len1==0||len2==0) return 0;
        int max_lcs=0;//设置当前最长公共字串长度0
        int start_i=0;
        vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));//设置二维数组存储str1[i-1]和str2[i-1]为公共子串最后一个字符的公共子串长度
        //初始化
        for(int i=1;i<=len1;i++)
        {
            for(int j=1;j<=len2;j++)
            {
                if(str1[i-1]==str2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1]+1;//如果str1[i-1]==str2[j-1]，以str1[i-1]和str2[i-1]为公共子串最后一个字符的公共子串长度
                }
                if(max_lcs<dp[i][j])
                {
                    max_lcs=max(max_lcs,dp[i][j]);//寻找最大的公共子串长度
                    start_i=i-1;
                }
            }
        }
        return str1.substr(start_i-max_lcs+1,max_lcs);
    }
};
复杂度分析
  • 时间复杂度：时间复杂度为$O(len(str1)*len(str2))$
  • 空间复杂度：需要设置一个二维数组存储信息，因此空间复杂度为$O(len(str1)*len(str2))$

方法三

思路分析

对方法二额外空间进一步优化，在方法二中设置了一个二维数组，实际上每次填充下一行的操作可以直接在第一行中进行更新，因此只需要一维数组即可存储信息。转移方程为：
dp[j]=\left\{ <br /> \begin{array}{**lr**} <br /> 0, & j=0 \\ <br /> dp[j-1]+1, & str1[i]=str2[j]\\ <br /> 0, & str1[i] !=str2[j] <br /> \end{array} <br />\right.

图解


核心代码 

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // write code here
        int len1=str1.size();
        int len2=str2.size();
        if(len1==0||len2==0) return 0;
        int max_lcs=0;//设置当前最长公共字串长度0
        int start_i=0;
        vector<int>dp(len2+1,0);//设置一维数组存储
        //初始化
        for(int i=0;i<len1;i++)
        {
            for(int j=len2-1;j>=0;j--)
            {
                if(str1[i]==str2[j])
                {
                    dp[j] = dp[j-1]+1;//str1[i]==str2[j]，以str1[i]和str2[j]结束的子串，长度加1
                }
                else dp[j]=0;
                if(max_lcs<dp[j])
                {
                    max_lcs=dp[j];
                    start_i=i;
                }
            }
        }
        return str1.substr(start_i-max_lcs+1,max_lcs);
    }
};
复杂度分析
  • 时间复杂度：时间复杂度同方法二，为$O(len(str1)*len(str2))$
  • 空间复杂度：额外使用一个一维数组，空间复杂度为$O(len(str2))$