HDU 1159 Common Subsequence

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 const int maxn = 1010;
 9 int dp[maxn][maxn];
10 char s1[maxn], s2[maxn];
11 
12 int main(void)
13 {
14     #ifdef LOCAL
15         freopen("1159in.txt", "r", stdin);
16     #endif
17 
18     while(cin >> s1 >> s2)
19     {
20         int len1, len2, i, j;
21         len1 = strlen(s1);
22         len2 = strlen(s2);
23         for(i = 1; i <= len1; ++i)
24             for(j = 1; j <= len2; ++j)
25             {
26                 if(s1[i-1] == s2[j-1])
27                     dp[i][j] = dp[i-1][j-1] + 1;
28                 else
29                     dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
30             }
31 
32         printf("%d\n", dp[len1][len2]);
33     }
34     return 0;
35 }