NYOJ 36(增量法解决LCS)

 1  
 2 #include<stdio.h>
 3 #include<string.h>
 4 #define N 1001
 5 char a[N],b[N];
 6 int d[N][N];
 7 int max(int m,int n)
 8 {
 9     return m>n?m:n;
10 }
11 int LCSL(int len1,int len2)
12 {
13     int i,j;
14     for(i=1;i<=len1;i++)
15         d[i][0]=0;
16     for(j=1;j<=len2;j++)
17         d[0][j]=0;
18     for(i=1;i<=len1;i++)
19         for(j=1;j<=len2;j++)
20             if(a[i-1]==b[j-1])
21                 d[i][j]=d[i-1][j-1]+1;
22             else
23                 d[i][j]=max(d[i][j-1],d[i-1][j]);
24     return d[len1][len2];
25 }
26 int main()
27 {
28     int T,len1,len2;
29     scanf("%d%*c",&T);
30     while(T--)
31     {
32         memset(a,0,sizeof(a));
33         memset(b,0,sizeof(b));
34         memset(d,0,sizeof(d));
35         scanf("%s%*c",a);
36         scanf("%s%*c",b);
37         len1=strlen(a);
38         len2=strlen(b);
39         printf("%d\n",LCSL(len1,len2));
40     }
41     return 0;
42 }