题解 | #最长公共子串#

class Solution {
public:
   string LCS(string s1, string s2) {
        s1=" "+s1,s2=" "+s2;
        int ma=0xc0c0c0c0;
        string res="";
        vector<pair<int,string>>dp(s2.length(),{0,""});
        for(int i=1;i<s1.length();i++)
        for(int j=s2.length()-1;j>=1;j--)
        {
            if(s1[i]==s2[j])dp[j].first=dp[j-1].first+1,dp[j].second=dp[j-1].second+s1[i];
            else dp[j]={0,""};
            if(ma<dp[j].first)ma=dp[j].first,res=dp[j].second;
        }
        return res;   
   }     
};