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

/*HJ65 查找两个字符串a,b中的最长公共子串*/
#include<iostream>
using namespace std;
int main()
{
    string a;
    string b;
    string shorty;
    string longy;
    int dp[350][350];
    cin>>a>>b;
    for(int i=0;i<=a.length();i++)
    {
        for(int j=0;j<=b.length();j++)
        {
            dp[i][0]=0;
            dp[0][j]=0;
        }
    }
    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;
            else dp[i][j]=0;
        }
    }
    int max=0,aa,bb;
    for(int i=0;i<=a.length();i++)
    {
        for(int j=0;j<=b.length();j++)
        {
        	if(a.length()<b.length())
        	{
        		if(dp[i][j]>max||dp[i][j]==max&&i<aa)
				{
					max=dp[i][j];
					aa=i;
					bb=j;
				}
			}
			else if(a.length()>=b.length())
			{
				if(dp[i][j]>max||dp[i][j]==max&&j<bb)
				{
					max=dp[i][j];
					aa=i;
					bb=j;
				}
			}        	
//           	cout<<dp[i][j]<<" ";
        }
//        cout<<endl;
    }
//    cout<<max<<" "<<s<<" "<<l<<endl;
    if(a.length()<b.length())
    cout<<a.substr(aa-max,max)<<endl;
    else if(a.length()>b.length())cout<<b.substr(bb-max,max)<<endl;
}