职业IT人论坛

 找回密码
 注册

扫一扫,访问微社区

搜索
2019PMP认证备考培训项目管理之家专场百度自然排名1-15天上首页,达标计费,无效退款.500+微信公众号程序模块,免费使用!
查看: 564|回复: 2

最长公共子序列

[复制链接]
找不到我 发表于 2011-10-6 10:33 | 显示全部楼层 |阅读模式
摘要:关于VC最长公共子序列的深入研究。

78701455261eba93b745aec4.jpg
算法思想
  一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。最长公共子序列就是求给定两个序列的一个最长公共子序列。动态规划可以有效的解决此问题。由最长公共子序列问题的子序列的最优子结构性质,可以建立子问题最优的递归关系。用c[j]记录序列Xi和Yi的最长公共子序列的长度,递归关系如下:
  0 i=0,j=0
  c[j]= c[i-1][j][j-1]+1 i,j> 0;xi==yj
  max c[j-1],c[i-1][j] I,j> 0;xi==yj
  在具体的算法设计中,以序列X= { x1,x2,x3,…,xm }和Y= {y1,y2,y3,…,ym}作为输入。输出三个数组c,b,temp。其中c[j]存储Xi和Yj的公共子序列的长度,b[j]记录c[j]的值是由哪一个子问题的解得到的,这在构造最长公共子序列时要用到。问题得最优解,即X和Y得最长公共子序列记录在temp[h]中。
源代码
  下面是在Microsoft Visual C++ 6.0中编写的求最长公共子序列的源程序,程序定义了最大得字符串长度为99,是将p48页的动态规划算法改写而来的。
  1.   #include <iostream.h>
  2.   #include <iomanip.h>
  3.   #define MAX 99
  4.   //typedef char MM;
  5.   void main()
  6.   { int i,j,m,n,h=0;
  7.   char x[MAX]={ ' ', ' '},y[MAX]={ ' ', ' '},b[MAX][MAX]={ ' '};
  8.   int c[MAX][MAX]={0};
  9.   char temp[MAX]={ ' '};
  10.   cout < < "**本程序可以求得字符数在99以内的任意两个字符串的最大公共子序列**\n ";
  11.   cout < < "请输入第一个字符串的长度m= ";
  12.   cin> > m;
  13.   cout < < "请输入第一个字符串(“回车”结束)\n如果输入的字符数超过m,则会出错!\nx[ " < <m < < "]= ";
  14.   for(i=1;i <=m;i++)
  15.   cin> > x[i]; //键盘输入x和y
  16.   cout < < "请输入第二个字符串的长度n= ";
  17.   cin> > n;
  18.   cout < < "请输入第二个字符串\ny[ " < <n < < "]= ";
  19.   for(i=1;i <=n;i++)
  20.   cin> > y[i];
  21.   for(i=1;i <=m;i++)c[i][0]=0; //动态规划开始
  22.   for(i=1;i <=n;i++)c[0][i]=0;
  23.   for(i=1;i <=m;i++)
  24.   for(j=1;j <=n;j++)
  25.   {if(x[i]==y[j])
  26.   {c[i][j]=c[i-1][j-1]+1;
  27.   b[i][j]= '\\ ';
  28.   }else
  29.   if(c[i-1][j]> =c[i][j-1])
  30.   { c[i][j]=c[i-1][j];
  31.   b[i][j]= '│ ';
  32.   }else{c[i][j]=c[i][j-1];
  33.   b[i][j]= '- ';
  34.   }
  35.   } //动态规划结束
  36.   cout < < "c[m][n]中的内容:\n ";
  37.   for(i=0;i <=m;i++)
  38.   {for(j=0;j <=n;j++)
  39.   cout < <c[i][j];
  40.   cout < <endl;
  41.   }
  42.   cout < < "b[m][n]中的内容:\n ";
  43.   for(i=1;i <=m;i++)
  44.   {for(j=1;j <=n;j++)
  45.   cout < <b[i][j];
  46.   cout < <endl;
  47.   }
  48.   i=m,j=n;
  49.   while(1)
  50.   {if(i==0││j==0) break;
  51.   if(b[i][j]== '\\ '){
  52.   temp[h++]=x[i]; //反序记录最长公共子序列到temp中
  53.   i=i-1,j=j-1;
  54.   }
  55.   else
  56.   if(b[i][j]== '│ ')
  57.   i=i-1;
  58.   else
  59.   j=j-1;}
  60.   cout < < "\nx[ " < <m < < "]和y[ " < <n < < "]的最长公共子序列为: ";
  61.   for(i=h-1;i> =0;i--) //格式化输出最长公共子序列
  62.   if(i==h-1)
  63.   if(h==1)
  64.   cout < < "LCS: < " < <temp[i] < < "> ";
  65.   else
  66.   cout < < "LCS: < " < <temp[i];
  67.   else
  68.   if(i==0)
  69.   cout < < ", " < <temp[i] < < "> ";
  70.   else
  71.   cout < < ", " < <temp[i];
  72.   cout < < "\n " < <endl;
  73.   }
复制代码
运算结果
  其实它的最长公共子序列不止一个,这里只输出了其中的一个。
总结分析
  在这个具体的算法中,还有可以改进的地方,比如在具体的求最大公共子序列中,可以不必要MAX的宏定义,只需将各数组设为具体的长度就可以节约不少的空间,大大降低程序的空间复杂度,但是为了键盘输入任意字符串,牺牲了很多的内存空间。在键盘输入字符串时,可以不用循环赋值,直接用cin> > x;cin> > y;这样就可以将这部分的时间复杂度从O(m+n)降到O(2),但有一个相关的问题没解决,所以我没这样赋值。程序总的时间复杂度为:O(mn+3m+3n).
heqifan1314 发表于 2011-11-8 21:10 | 显示全部楼层
为什么我的学习币是-5
很想看看你啦 发表于 2012-1-12 22:51 | 显示全部楼层
这贴好强大的
您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|手机版|网站帮助|职业IT人 ( 粤ICP备12053935号 )

GMT+8, 2019-3-21 13:50 , Processed in 0.139703 second(s), 27 queries , Gzip On.

Powered by Discuz! X3.2

© 2001-2018 Comsenz Inc.

快速回复 返回顶部 返回列表