问题描述
给定两个字符串s1s2s3…sn和t1t2…tn。求出两个字符串最长的公共子序列的长度。字符串s1s2s3…sn的子序列指可以表示为si1si2…sim(i1<i2<…<im)的序列。 限制条件 1<=n,m<=1000
样例输入
4
4
abcd
brcd
样例输出
3
代码
#include
<iostream
>
#include
<algorithm
>
#include
<string
.h
>
#include
<cstdio
>
using namespace std
;
int dp
[1000][1000];
char s
[1005],t
[1005];
int
main()
{
int n
,m
;
scanf("%d%d",&n
,&m
);
getchar();
for(int i
= 0;i
<n
;i
++)
{
scanf("%c",&s
[i
]);
}
getchar();
for(int i
= 0;i
<m
;i
++)
{
scanf("%c",&t
[i
]);
}
for(int i
= 0;i
<=n
;i
++)
{
for(int j
= 0;j
<=m
;j
++)
{
if(s
[i
]==t
[j
])
{
dp
[i
+1][j
+1] = dp
[i
][j
]+1;
}
else
{
dp
[i
+1][j
+1] = max(dp
[i
][j
+1],dp
[i
+1][j
]);
}
}
}
printf("%d\n",dp
[n
][m
]);
return 0;
}
转载请注明原文地址:https://blackberry.8miu.com/read-10493.html