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

//
//
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
    string a,b;
    cin>>a>>b;
    vector<vector<int>> dp(a.length()+5,vector<int>(b.length()+5,0));
    int Index=0,maxL=0;
    bool aflag;
    if(a.length()>=b.length()){
        aflag=false;
    } else aflag=true;

    //i(j)指的是a(b)的第i(j)个字符
    //dp[i][j]为当前a串的以第i个字符为结尾的子串，与b的以第j个字符为结尾的子串的最长公共子串长度，
    //a[i]==b[j]
    for(int i=1;i<=a.length();i++){
        for(int j=1;j<=b.length();j++){
            if(a[i-1]==b[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
                //当目前最长子串出现时,记录其在较短串中的位置
                if(dp[i][j]>maxL){
                    Index=aflag?i:j;
                    maxL=dp[i][j];
                }
                //相同长度的子串出现，比较谁在较短串中位置更早出现
                else if(dp[i][j]==maxL){
                    Index=min((aflag?i:j),Index);
                }
            }
        }
    }
    cout<<(aflag?a.substr(Index-maxL,maxL):b.substr(Index-maxL,maxL));
    return 0;
}