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

动态规划，以第i和j个字符结尾的公共子串若存在则长度为dp[i][j]，若str1[i]==str2[j]则dp[i][j]=dp[i-1][j-1]+1。求出最长并输出就行了，这个动态规划还可以压缩

#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<vector<int>> dp(m,vector<int>(n,0));
        for(int i =0;i<m;i++){
            if(str1[i]==str2[0]) dp[i][0]=1;
        }
        for(int j =0;j<n;j++){
            if(str1[0]==str2[j]) dp[0][j]=1;
        }
        int maxlen = -1,end = 0;
        for(int i = 1;i<m;i++){
            
            for(int j = 1;j<n;j++){
                if(str1[i]==str2[j]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }
                if(dp[i][j]>maxlen) {
                    maxlen=dp[i][j];
                    end = i;
                }
            }
        }
        
        string out = str1.substr(end-maxlen+1,maxlen);
        cout<<out<<endl;
    }
}