算法分析与设计-作业9-求最长公共子序列
1.问题
给定序列 ：
求X和Y的最长公共子序列。
2.解析
3.设计
算法一：给出最长字串长度
算法二：f(B,i,j) 输出最长字串
实例：
X=<A,B,C,D>
Y=<B,A,D>
m=0-4
n=0-3
求最长子序列的长度：
(1)i=1
A.j=1 X.A<>Y.B : C[1,1]=max(C[1,0],C[0,1])=max(0,0)=0 , 删除Y
B.j=2 X.A=Y.A : C[1,2]=C[0,1]+1=1 , 删除两个
C.j=3 X.A<>Y.D : C[1,3]=max(C[1,2],C[0,3])=max(1,0)=1 , 删除Y
(2)i=2
A.j=1 X.B=Y.B : C[2,1]=C[1,0]+1=1,删除两个
B.j=2 X.B<>Y.A : C[2,2]=max(C[2,1],C[1,2])=max(1,0)=1 , 删除Y
C.j=3 X.B<>Y.D : C[2,3]=max(C[2,2],C[1,3])=max(1,1)=1 , 删除Y
(3)i=3
A.j=1 X.C<>Y.A : C[3,1]=max(C[3,0],C[2,1])=max(0,1)=1 , 删除X
B.j=2 X.C<>Y.B : C[3,2]=max(C[3,1],C[2,2])=max(1,1)=1 , 删除Y
C.j=3 X.C<>Y.D : C[3,3]=max(C[3,2],C[2,3])=max(1,1)=1 , 删除Y
(4)i=4
A.j=1 X.D<>Y.A : C[4,1]=max(C[4,0],C[3,1])=max(0,1)=1 , 删除X
B.j=2 X.D<>Y.B : C[4,2]=max(C[4,1],C[3,2])=max(1,1)=1 , 删除Y
C.j=3 X.D=Y.D : C[4,3]=C[3,2]+1=2 , 删除两个
输出最长子序列：
(1)x=4,y=3
查表(4,3) : 删除两个
X=<A,B,C,D>
Y=<B,A,D>
(2)x=3,y=2
查表(3,2)：删除y
X=<A,B,C>
Y=<B,A>
(3)x=3,y=1
查表(3,1)：删除x
X=<A,B,C>
Y=< B>
(4)x=2,y=1
查表(2,1)：删除两个
X=<A,B>
Y=< B>
(5)x=1,y=0
输出：<B,D>
4.分析
复杂度：O(m*n)