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

#include <iostream>
#include <string>
#include <vector>
using namespace std;
dp[i][j]为：以s1[i]为结尾的s1子串与以s2[j]为结尾的s2子串的最长公共子串长度
int main() {
    string x,y,s1,s2;
    cin >> x >> y;
    s1=x.size()>y.size()?y:x;
    s2=x.size()<=y.size()?y:x;
    int m=s1.size();
    int n=s2.size();
    int result=0;
    int end=0;
    vector<vector<int>> dp(m+1,vector<int>(n+1,0));
    for(int i=1;i<=m;++i){
        for(int j=1;j<=n;++j){
            if(s1[i-1]==s2[j-1]){
                dp[i][j]=1+dp[i-1][j-1];
            }
            if(dp[i][j]>result){
                end=i;
                result=dp[i][j];
            }
        }
    }
    cout << s1.substr(end-result,result);
}
// 64 位输出请用 printf("%lld")