晕，最基本的dp题，最长公共子序列。。。。。。竟然没有考虑到空格，衰衰地wa了几次。。。。。。
View Code
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4
5 const int maxn = 1010;
6 int dp[maxn][maxn];
7 char s1[maxn];
8 char s2[maxn];
9
10 int main()
11 {
12 while(gets(s1) != NULL)
13 {
14 gets(s2);
15 int len1 = strlen(s1);
16 int len2 = strlen(s2);
17
18 memset(dp,0,sizeof(dp));
19 for(int i = 0;i < len2;i ++)
20 {
21 for(int j = 0;j < len1;j ++)
22 {
23 if(s2[i] == s1[j])
24 dp[i + 1][j + 1] = dp[i][j] + 1;
25 else
26 {
27 dp[i + 1][j + 1] = std::max(dp[i + 1][j],dp[i][j + 1]);
28 dp[i + 1][j + 1] = std::max(dp[i +1 ][j+1],dp[i][j]);
29 }
30 }
31 }
32 printf("%d\n",dp[len2][len1]);
33 }
34
35 return 0;
36 }