链接:https://ac.nowcoder.com/acm/contest/301/E
来源:牛客网
题目描述
小乐乐有字符串str1,str2。
小乐乐想要给他们找朋友。
小乐乐想知道在这两个字符串中最多能匹配出多长的相同子串(可非连续)。
输入描述:
第一行输入字符串str1; 第二行输入字符串str2; 数据保证字符串长度小于1000,且非空,字符串仅由小写字母组成。
输出描述:
输出最长相同子串的长度。
示例1
输入
asd ad
输出
2
题意:略
题解:详细请看代码:
#include <iostream>
using namespace std;
const int MAX = 1200;
int dp[MAX][MAX];
int main(){
string s1,s2;
cin >> s1 >> s2;
for (int i = 1; i <= s1.size();i++){//最长公共子序列非连续 模板
for (int j = 1; j <= s2.size();j++){
if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
cout << dp[s1.size()][s2.size()] << endl;
return 0;
}