求最长公共子串的两种解法

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。 

数据范围： 1≤∣str1∣,∣str2∣≤50001≤∣str1∣,∣str2∣≤5000
要求： 空间复杂度 O(n2)，时间复杂度 O(n2)

实例：

输入：
"1AB2345CD","12345EF"
返回值：
"2345"

备注：

1≤∣str1∣,∣str2∣≤5000

因为本题时间复杂度满足n^2即可，所以我们采用暴力枚举的方法将两个字符串进行逐个字符比价然后求出最长子串即可。

法一：

class Solution {
public:
    string LCS(string str1, string str2) {
    string ans;
    string temp;
    for(int i=0;i<str1.size();i++){
        for(int j=0;j<str2.size();j++){
            if(str1[i]==str2[j]){
                int x=i,y=j;
                while (str1[x]==str2[y]) {
                x++;y++;
                temp+=str1[x-1];
                }
                if(temp.size()>ans.size()){
                    ans=temp;
                }
                temp.clear();
            }
        }
    }
    return ans;
    }
};

法一思路比较简单，通过定义两个新的字符串ans和temp，通过双重循环将原输入的str1和str2进行比较，如果有字符相等则新定义两个整形x、y来记录此时相同的字符分别在str1和str2中的位置i和j，再通过循环判断该位置后面的字符是否也相等，将寻找出的子串存储在temp中，接着比较ans和temp的长度，如果temp>ans则ans=temp,最后将temp清空继续下一轮循环。

法二：

class Solution {
public:
    string LCS(string str1, string str2) 
    {
      vector<vector<int>> dp(str1.size()+1,vector<int>(str2.size()+1,0));
      int max=0,pos=0;
      for(int i=0;i<str1.size();++i)
      {
        for(int j=0;j<str2.size();++j)
        {
            if(str1[i]==str2[j])
            {
                dp[i+1][j+1]=dp[i][j]+1;
            }
            if(dp[i+1][j+1]>max)
            {
                max=dp[i+1][j+1];
                pos=i;
            }
        }
      }
      return str1.substr(pos-max+1,max);
    }
};

法二通过开辟一个二维数组来存储存在的相同子串长度有哪些以及对应位置，通过  dp[i+1][j+1]=dp[i][j]+1来实现连续子串长度的增加，最后通过找出最大子串长度然后截取其对应在str1中的位置并返回。