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

#include <iostream>
#include <bits/stdc++.h>
#include <vector>
using namespace std;

string LCS(string str1,string str2) {
  		//我们的代码需要str1的长度小于str2的长度
        if(str1.size()>str2.size()){
            swap(str1,str2);
        }
        int m = str1.size();
        int n = str2.size();
        //dp[m][n]表示str1的前i个字符和str2的前j个字符（以其为结尾）的最长公共子串长度
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        int maxlen = 0;
        int end = 0;
        for(int i =1;i<=m;i++){
            for(int j = 1;j<=n;j++){
                if(str1[i-1]==str2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    //dp[i][j] = max(dp[i-1][j],dp[i][j-1]);这是子序列
                    dp[i][j] = 0;//子串是要求连续的，因此不等就断掉了
                }
                if(dp[i][j]>maxlen) {maxlen = dp[i][j];end = i-1;}
            }
        }
        if(maxlen==0) return "-1";
        else return str1.substr(end-maxlen+1, maxlen);
        
}
int main(){
    string s1,s2;
    while(cin>>s1>>s2)
        cout<<LCS(s1, s2)<<endl;
}


    

// 64 位输出请用 printf("%lld")