Common Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 38003 Accepted Submission(s): 17422
Problem Description
A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X =
Sample Input
abcfbc abfcab
programming contest
abcd mnp
Sample Output
4
2
0
最长公共子序列
1 #include
2 #include
3 #include
4 using namespace std;
5
6 const int MAXN = 512;
7 int dp[MAXN][MAXN];
8
9 int main()
10 {
11 char s1[MAXN], s2[MAXN];
12
13 int i, j;
14 int len1, len2;
15
16 while (~scanf("%s%s", s1 + 1, s2 + 1)) {
17 len1 = strlen(s1 + 1);
18 len2 = strlen(s2 + 1);
19 memset(dp, 0, sizeof(dp));
20
21 for (i = 1; i <= len1; ++i) {
22 for (j = 1; j <= len2; ++j) {
23 if (s1[i] == s2[j]) {
24 dp[i][j] = dp[i - 1][j - 1] + 1;
25 } else {
26 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
27 }
28 }
29 }
30
31 printf("%d\n", dp[len1][len2]);
32 }
33
34 return 0;
35 }
相关文章
发表评论