最长公共子序列

摘要：关于VC最长公共子序列的深入研究。


算法思想
　　一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列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).

为什么我的学习币是-5

这贴好强大的