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

#include <algorithm>
#include <any>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    if(str1.length() > str2.length()) swap(str1, str2);//规定str1为较短串
    vector<vector<int>> dp(str1.length()+1, vector<int>(str2.length()+1, 0));
    int subStrLen = 0;//记录当前求得最长公共子串的长度
    int left = 0;//记录当前求得最长公共子串在str1中的起始位置
    for(int i = 1; i <= str1.length(); i++){
        for(int j = 1; j <= str2.length(); j++){
            if(str1[i-1] == str2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1;
                if(dp[i][j] > subStrLen){
                    subStrLen = dp[i][j];
                    left = i - subStrLen;
                }
            }
        }
    }
    cout << str1.substr(left, subStrLen) << endl;
    return 0;
}