最长公共子序列(1)

会计考友

最长公共子序列(1)
一、算法思想
- _5 u+ e' P0 N+ U5 ^( ~! K　　一个给定序列的子序列是在该序列中删去若干元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X 和Y的公共子序列。最长公共子序列就是求给定两个序列的一个最长公共子序列。动态规划可以有效的解决此问题。由最长公共子序列问题的子序列的最优子结构性质，可以建立子问题最优的递归关系。用c[j]记录序列Xi和Yi的最长公共子序列的长度，递归关系如下：
% x/ k, H8 |4 W( i7 K. w# ?6 i+ l　　0 i=0,j=0
. O$ G' i; t0 @8 l　　c[j]= c[i-1][j][j-1]+1 i,j> 0;xi==yj
3 _* Z! [& D7 M3 {9 f9 C  @　　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]中。
　　二、源代码
' U" C: |8 t% Z) p3 b　　下面是在Microsoft Visual C++ 6.0中编写的求最长公共子序列的源程序，程序定义了最大得字符串长度为99，是将p48页的动态规划算法改写而来的。
, r' F) ~2 q7 v) ~) w. v　　#include
　　#include
　　#define MAX 99
　　//typedef char MM;
　　void main()
　　{ int i,j,m,n,h=0;
　　char x[MAX]={ ' ', ' '},y[MAX]={ ' ', ' '},b[MAX][MAX]={ ' '};
3 W" n: \: q9 C' `: I" K0 g2 h　　int c[MAX][MAX]={0};
　　char temp[MAX]={ ' '};
8 g0 I# Q3 W, f# b+ T- `( z+ ]4 J　　cout < < "**本程序可以求得字符数在99以内的任意两个字符串的最大公共子序列**\n ";
& I, G- X7 w' `+ a: G7 ?4 }　　cout < < "请输入第一个字符串的长度m= ";
　　cin> > m;
　　cout < < "请输入第一个字符串(“回车”结束)\n如果输入的字符数超过m,则会出错!\nx[ " </pp　　for(i=1;i =m;i++)/pp　　cin > x; //键盘输入x和y
# W) n8 t4 c$ D9 J) b& T# r　　cout < < "请输入第二个字符串的长度n= ";
0 I; Y5 K4 s/ _8 ~" G3 P9 r　　cin> > n;