bon

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  46 Posts :: 0 Stories :: 12 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

这一篇讲我对最长公共子序列(LCS)的理解,之前只是强记了公式,现在有了较好的理解。

主要是要理解这个问题具有最优子结构性质。

设序列的LCS是,则

(1) 若,则,且的LCS;

(2) 若,且,则的LCS;

(3) 若,且,则的LCS 。

证明:(1) 若,说明在的后面加上,可以得到一个长为k+1的新序列:,这与
                  的LCS矛盾。另外若不是的LCS,那么我们只用就可以得到一个长度至少为k的子序列,再这个子序列
                  后面再加上,就可以用构造得到一个长为k+1的子序列,这也产生了矛盾。
         
            (2) 若有比更长的LCS,则这个LCS同样是的一个长于k的LCS,矛盾。(3)的证明类似。

思考:(2)中的结论"的LCS "能否改成"的LCS" 呢?因为可能是最后一个元素,那么的LCS就不是
                  了,而是更小的一个序列。
               
                  其实(2)的条件暗示着可能就是,当然也有可能不是,但是不管怎么样, 肯定是的LCS。

                  下面的图说明了这两种情况:

                  
由此我们可以得到如下的状态转移方程:



下面就是题目代码啦,很简单,没什么好说的。

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 char a[100001],b[100001];
 6 
 7 void dp()
 8 {
 9     int n=strlen(a),m=strlen(b);
10     int i,j;
11     int d[2][100000];
12     int flag=1;
13     for(i=0;i<=n;i++) d[0][i]=0;
14     for(i=1;i<=m;i++){
15         for(j=0;j<=n;j++){
16             if(j==0) d[flag][j]=0;
17             else{
18                 if(b[i-1]==a[j-1]) d[flag][j]=d[1-flag][j-1]+1;
19                 else{
20                     d[flag][j]=(d[flag][j-1]>d[1-flag][j])?d[flag][j-1]:d[1-flag][j];
21                 }
22             }
23             //printf("%d ",d[flag][j]);
24         }
25         //printf("\n");
26         flag=1-flag;
27     }
28     //printf("%d\n",d[1-flag][n]);
29     if(d[1-flag][n]==n)    printf("Yes\n");
30     else printf("No\n");
31     return;
32 }
33 
34 int main()
35 {
36     while(cin>>a>>b){
37         dp();
38     }
39     return 1;
40 }
posted on 2008-05-27 15:46 bon 阅读(575) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Google PageRank 
Checker - Page Rank Calculator