题解 | #查找两个字符串a,b中的最长公共子串#

压缩一下，空间复杂度一下就降下来了，不停的更新每一行就行了，把短的字符串弄到第一行。

其实可以看出有公共子串其实就是矩阵里不为0的位置连在一起。

```#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    string str1,str2;
    while(cin>>str1>>str2){
        int m = str1.size();
        int n = str2.size();
        if(m>n){
        swap(str1, str2);
        m = str1.size();
        n = str2.size();
        }
        vector<int> dp(n,0);
        for(int i =0;i<n;i++){
            if(str1[0]==str2[i]) dp[i]=1;//这里是边界条件
        }
        
        int maxlen = -1,end = 0;
        int temp,update;
        for(int i = 1;i<m;i++){//注意这里要小的字符串在外层，这样相同的长度会选择
//前面的
            if(str1[i-1]==str2[0])dp[0]=1;
            else dp[0]=0;
            update=dp[0];//第一列先给更新上
            for(int j = 1;j<n;j++){
                temp = dp[j];//保存所在列的上一行
                if(str1[i]==str2[j]){
                   dp[j] = update+1;//如果可以就更新所在列的这一行
                }
                else dp[j] = 0;不行的话就更新为0说明中断了
                update = temp;把上一行的所在列赋给下一轮要用的值。
                if(dp[j]>maxlen) {
                    maxlen=dp[j];更新最长长度
                    end = j;//最长 公共子串的末尾
                }
            }
        }
        
        string out = str2.substr(end-maxlen+1,maxlen);//找到起始位置开始拷贝。
        cout<<out<<endl;
    }
}