Yiner的ACM

成长的痕迹
<2011年3月>
日一二三四五六
272812345
6789101112
13141516171819
20212223242526
272829303112
3456789

统计

  • 随笔 - 29
  • 文章 - 0
  • 评论 - 2
  • 引用 - 0

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

最长公共子序列 记录子序列~
 1#include<stdio.h>
 2#include<string.h>
 3char a[101],b[101],d[101];
 4int c[101][101];
 5int max(int x,int y)
 6{
 7    if(x>y)
 8    return x;
 9    else
10    return y;
11}
12int main()
13{
14    int lena,lenb,i,j,k,m;
15    while(scanf("%s%s",a+1,b+1)!=EOF)
16    {
17        m=0;
18        memset(d,0,sizeof(d));
19        lena=strlen(a+1);
20        lenb=strlen(b+1);
21        for(i=0;i<=lena;i++)
22             c[0][i]=0;
23             for(j=0;j<=lenb;j++)
24                c[j][0]=0;
25                k=0;
26                for(i=1;i<=lena;i++)
27                for(j=1;j<=lenb;j++)
28                 {
29                     if(a[i]==b[j])
30                       {
31                           c[i][j]=c[i-1][j-1]+1;
32                           if(c[i][j]>m)
33                           {
34                               d[k]=a[i];
35                              k++;
36                           }
37
38                       }
39                    else
40                        c[i][j]=max(c[i-1][j],c[i][j-1]);
41                    if(c[i][j]>m)
42                        m=c[i][j];
43                 }
44                 printf("%d\n",c[lena][lenb]);
45                 printf("%s\n",d);
46    }
47    return 0;
48}
49

posted on 2011-03-05 21:35 Yiner 阅读(200) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理