hdu1159Common Subsequence(最长公共子序列）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int maxn=1010;
 6 char s[maxn],t[maxn];
 7 int dp[maxn][maxn];
 8 
 9 int main()
10 {
11     while(scanf("%s",s+1)!=EOF)
12     {
13         memset(dp,0,sizeof(dp));
14         scanf("%s",t+1);
15         int sl=strlen(s+1);
16         int tl=strlen(t+1);
17         for(int i=1;i<=sl;i++)
18         {
19             for(int j=1;j<=tl;j++)
20             if(s[i]==t[j]) dp[i][j]=dp[i-1][j-1]+1;
21             else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
22         }
23         printf("%d\n",dp[sl][tl]);
24     }
25 }