sijing

经典算法题目——最长公共子序列问题

 

给定两个序列
X = { x1 , x2 , ... , xm }
Y = { y1 , y2 , ... , yn }
求X和Y的一个最长公共子序列

举例
X = { a , b , c , b , d , a , b }
Y = { b , d , c , a , b , a }
最长公共子序列为
LSC = { b , c , b , a }

分析:

最长公共子序列问题具有最优子结构性质


X = { x1 , ... , xm }
Y = { y1 , ... , yn }
及它们的最长子序列
Z = { z1 , ... , zk }

1、若 xm = yn , 则 zk = xm = yn,且Z[k-1] 是 X[m-1] 和 Y[n-1] 的最长公共子序列
2、若 xm != yn ,且 zk != xm , 则 Z 是 X[m-1] 和 Y 的最长公共子序列
3、若 xm != yn , 且 zk != yn , 则 Z 是 Y[n-1] 和 X 的最长公共子序列

由性质导出子问题的递归结构

当 i = 0 , j = 0 时 ,        c[i][j] = 0
当 i , j > 0 ; xi = yi 时 ,  c[i][j] = c[i-1][j-1] + 1
当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }

////////////////////////////////////////
这种分析方法比较有用,值得保存,book
 ----《计算机机算法设计与分析》电子工业出版社
////////////////////////////////////////

// 书中只有关键部分的代码,现在已经补全
// 源程序

#include "iostream.h"
#include "iomanip.h"

#define max 100

void LCSLength( int m , int n , char *x , char *y , char *b )
{
         int i , j , k;
         int c[max][max];

         for( i = 1 ; i <= m ; i++ )
        {
              c[i][0] = 0;
        }
        for( i = 1 ; i <= n ; i++ )
        {
              c[0][i] = 0;
        }
       for( i = 1 ; i <= m ; i++ )
       {
              for( j = 1 ; j <= n ; j++ )
             {
                    if( x[i-1] == y[j-1] )
                   {
                             c[i][j] = c[i-1][j-1] + 1;
                             k = i * ( n + 1 ) + j;
                             b[k] = '\\';
                   }
                  else if( c[i-1][j] >= c[i][j-1] )
                 {
                            c[i][j] = c[i-1][j];
                            k = i * ( n + 1 ) + j;
                            b[k] = '|';
                 }
                 else
                {
                        c[i][j] = c[i][j-1];
                       k = i * ( n + 1 ) + j;
                          b[k] = '-';
                 }
            }
       }

}
void LCS( int i , int j , char *x , char *b , int width )
{
           if( i == 0 || j == 0 )
                   return;
          int k = i * ( width + 1 ) + j;
          if( b[k] == '\\' )
         {
                LCS( i - 1 , j - 1 , x , b , width );
                cout<<x[i]<<endl;
         }
         else if( b[k] == '|' )
        {
                  LCS( i - 1 , j , x , b , width );
         }
        else
        {
                 LCS( i , j - 1 , x , b , width );
         }
}

void main()
{
       char x[max] = { 'a' , 'b' , 'c' , 'b' , 'd' , 'a' , 'b' };
      char y[max] = { 'b' , 'd' , 'c' , 'a' , 'b' , 'a' };
      int m = 7;
      int n = 6;
      char b[max] = { 0 };

      LCSLength( m , n , x , y , b );
      LCS( m , n , x , b , n );

      cout<<endl<<endl;
}

////////////////////////////////////////

posted on 2010-04-25 19:33 宇骐 阅读(2697) 评论(1)  编辑 收藏 引用

评论

# re: 经典算法题目——最长公共子序列问题 2010-04-27 14:03 Geek.tan

还可以优化内存的,仔细想想,每次c[i][j] 中只利用了才c[i-1][] 和c[i][]这两列的数组,想想看该如何节约内存。  回复  更多评论   


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


<2010年4月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜