题目地址：https://ac.nowcoder.com/acm/contest/301/E

题目描述

小乐乐有字符串str1,str2。

小乐乐想要给他们找朋友。

小乐乐想知道在这两个字符串中最多能匹配出多长的相同子串（可非连续）。

输入描述:

第一行输入字符串str1;

第二行输入字符串str2;

数据保证字符串长度小于1000，且非空，字符串仅由小写字母组成。

输出描述:

输出最长相同子串的长度。

 

示例1

输入

asd
ad

输出

2

 

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)

int dp[1005][1005];

int main() 
{
	string s1,s2;
	int i,j;
	mem(dp,0);
	cin>>s1>>s2;
	for(i=1;i<=s1.length();i++)
	{
		for(j=1;j<=s2.length();j++)
		{
			if(s1[i-1]==s2[j-1])
				dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j]);
			else
				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
		}
	}
	cout<<dp[s1.length()][s2.length()]<<endl;
	return 0;
}