YYHS1619(tyvj 1050)_一个字符串a的子串被定义成从a中顺次选出若干个字符构成的串。如a=“cdaad" ,顺次选…

时间限制: 1 Sec 内存限制: 128 MB
题目描述
一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad” ,顺次选1，3，5个字符就构成子串” cad” ,现给定两个字符串，求它们的最长共公子串。

输入
第一行两个字符串用空格分开。

输出
最长子串的长度。

样例输入
abccd aecd
样例输出
3
提示
两个串的长度均小于2000

我们令两个串为s1,s2；f[i][j]为s1前i个字符,s2前j个字符最长的公共子串长度。
则我们可以发现
当s1[i]=s1[j]时 f[i][j]=f[i-1][j-1]+1（当然f[i-1][j-1]+1一定大于等于max(f[i-1][j],f[i][j-1])）
当s1[i]!=s1[j]时 f[i][j]=max(f[i-1][j],f[i][j-1])

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s1[2010],s2[2010];
int dp[2010][2010];
int Max(int x,int y) { return (x>y)?x:y;}
int main()
{
    scanf("%s%s",s1+1,s2+1);
    int len1=strlen(s1+1),len2=strlen(s2+1);
    for (int i=1;i<=len1;i++)
        for (int j=1;j<=len2;j++)
        if (s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=Max(dp[i][j-1],dp[i-1][j]);
    cout<<dp[len1][len2]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18