HDU1159最长公共子序列LCS

评测点

HDU1159

题目

【题意】
求两个字符串最长公共子序列的长度,
最长公共子序列强调位置的前后关系不变,
但不在乎是否连续,不唯一
【输入样例】
abbccdss aeebfcaadb
【输出样例】
4

某解释

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
char s[1010],s1[1010];
int f[1010][1010];
int main(int argc, char *argv[])
{
scanf("%s %s",s+1,s1+1);
int l1=strlen(s+1),l2=strlen(s1+1);
for(int i=1;i<=l1;i++)
for(int j=1;j<=l2;j++)
{
if(s[i]==s1[j]) f[i][j]=f[i-1][j-1]+1;
else f[i][j]=mymax(f[i-1][j],f[i][j-1]);
}
printf("%d",f[l1][l2]);
}

分析:
a=abc
b=1abc
n=3
m=4
i=2 4//字符串2的位置
j=2 3//字符串1的位置
s=
0 0 0 0
1 1 1 1
0 2 2 2
0 0 3 3

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/ddc4.html
转载请注明出处,谢谢!