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

#include <bits/stdc++.h>

using namespace std;

//dp
//dp[i][j]表示 到s1第i个,到s2第j个为止 的公共子串长度 (其中s1较短)
void longestCommonSubsequence(string s1, string s2, string& res) {
    vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
    int maxLength = INT_MIN, end = 0; //end表示字符串的末位位置 (最大不超过s1的长度)
    
    for(int i = 1; i <= s1.size(); i++){
        for(int j = 1; j <= s2.size(); j++){
            if(s1[i - 1] == s2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1; //则增加长度
            }
            else{
                dp[i][j] = 0; // //该位置为0
            }
            
            if(dp[i][j] > maxLength){ //更新最大长度
                maxLength = dp[i][j];
                end = i - 1; //
            }
        }
    }

    res = s1.substr(end - maxLength + 1, maxLength);
}


int main(){
    string s1 = "";
	string s2 = "";

	getline(cin, s1);
	getline(cin, s2);
    
    if(s1.length() > s2.length()){
        swap(s1, s2); //使较小的字符串在前
    } 
            
	string res = "";
	longestCommonSubsequence(s1, s2, res);
	cout << res << endl;
    
    return 0;
}