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

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    string s,p;
    while(cin>>s>>p)
    {
        if(s.size()>p.size())
        {
            swap(s,p);
        }
        vector<vector<int>>dp(s.size(),vector<int>(p.size()));
        int maxLen=0;
        for(int i=0;i<s.size();i++)
        {
            for(int j=0;j<p.size();j++)
            {
                if(s[i]==p[j])
                {
                    if(i==0||j==0)
                    {
                        dp[i][j]=1;
                    }
                    else
                    {
                        dp[i][j]=dp[i-1][j-1]+1;
                    }
                    if(dp[i][j]>maxLen)
                    {
                        maxLen=dp[i][j];
                    }
                }
                else
                {
                    dp[i][j]=0;
                }
            }
        }
        string res;
        int endindex=0;
        for(int i=0;i<s.size();i++)
        {
            bool flag=false;
            for(int j=0;j<p.size();j++)
            {
                if(dp[i][j]==maxLen)
                {
                    endindex=i;
                    flag=true;
                    break;
                }
            }
            if(flag)break;
        }
        int startindex=endindex-maxLen+1;
        while(maxLen--)
        {
            res.push_back(s[startindex++]);
        }
        cout<<res<<endl;
        
    }
}