2.3最长公共子序列问题
   和前面讲的有所区别，这个问题的不涉及走向。很经典的动态规划问题。
例题16


最长公共子序列
(lcs.pas/c/cpp)
【问题描述】
    一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X= < x1, x2,…, xm>，则另一序列Z= < z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 < i1, i2,…, ik>，使得对于所有j=1,2,…,k有 Xij=Zj
    例如，序列Z=是序列X=的子序列，相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若子字符串是什么X= < A, B, C, B, D, A, B>和Y= < B, D, C, A, B, A>，则序列是X和Y的一个公共子序列，序列也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4
的公共子序列。
    给定两个序列X= < x1, x2, …, xm>和Y= < y1, y2, … , yn>，要求出X和Y的一个最长公共子序列。
【输入文件】
    输入文件共有两行，每行为一个由大写字母构成的长度不超过200的字符串，表示序列X和Y。
【输出文件】
    输出文件第一行为一个非负整数，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出文件仅有一行输出一个整数0，否则在输出文件的第二行输出所求得的最长公共子序列(也用一个大写字母组成的字符串表示。
【输入样例】
ABCBDAB
BDCBA
【输出样例】
4
BCBA
【问题分析】
这个问题也是相当经典的。。
这个题目的阶段很不明显，所以初看这个题目没什么头绪，不像前面讲的有很明显的上一步，上一层之类的东西，只是两个字符串而且互相没什么关联。
但仔细分析发现还是有入手点的：
既然说是动态规划，那我们首先要考虑的就是怎么划分子问题，一般对于前面讲到的街道问题和数塔问题涉及走向的，考虑子问题时当然是想上一步是什么？但这个问题没有涉及走向，也没有所谓的上一步，该怎么办呢？
既然是求公共子序列，也就有第一个序列的第i个字符和第二个序列的第j个字符相等的情况。
那么我们枚第一个序列（X）的字符，和第二个序列（Y）的字符。
显然如果X[i]=Y[j]那么起点是1（下面说的子序列都是起点为1的），长度为i的子序列和长度为j的子序列的最长公共子序列就是长度为i-1和长度为j-1 的子序列中最长的公共子序列加上X[i]或Y[j]。
那要是不相等呢？
如果不相等，也就是说第一个序列长度为I的子序列和第二个序列中长度为j的子序列的公共子序列中X[i]和Y[j]不同时出现。也就是说第一个序列长度为i的子序列和第二个序列中长度为j的子序列的公共子序列是第一个序列长度为i的子序列和第二个序列中长度为j-1的子序列或第一个序列长度为i-1的子序列和第二个序列中长度为j的子序列的公共子序列中一个更长的。
给定两个序列
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] }

【参考程序】

#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;
#define max 100
ifstream fin("LCS.IN");
ofstream fout("LCS.OUT");
int total=0;
void LCSLength( int m , int n , char *x , char *y , char *b )
{
  int i , j , k;
  int c[max][max];
  memset(c,0,sizeof(c));

  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 );
        fout<<x[i];
        total++;
     }
   else if( b[k] == '|' )
          {
            LCS( i - 1 , j , x , b , width );
           }
        else
           {
            LCS( i , j - 1 , x , b , width );
           }
}

int main()
{
  char x[max];
  // = { 'a' , 'b' , 'c' , 'b' , 'd' , 'a' , 'b' };
  char y[max];
  // = { 'b' , 'd' , 'c' , 'a' , 'b' , 'a' };
  fin>>x>>y;
  int m,n;
   m = strlen(x);
   n = strlen(y);
   char b[max];
   memset(b,'0',sizeof(b));
   LCSLength( m , n , x , y , b );
   LCS( m , n , x , b , n );
   fout<<endl;
   fout<<total<<endl;
  return 0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。