最长公共子序列问题

1、WordWord文档WordWord文档实验三最长公共子序列问题实验环境本实验采用java语言编写实现，环境：JDK1.8,编译器：eclipse实验目的通过最长公共子序列问题，巩固并详细分析动态规划思想和解题步骤。设计思路最长公共子序列的定义为：设有两个序列SJLm和S21.n，需要寻找它们之间的一个最长公共子序列。例如，假定有两个序列：S1：INTHEBEGINNINGS2：ALLTHINGSARELOST则%和S2的一个最长公共子序列为THING。又比如：S1：ABCBDABS2：BDCABA则它们的一个最长公共子序列为BCBA。这里需要注意的是，一个子序列不一定必须是连续的，即中间可被

2、其他字符分开，单它们的顺序必须是正确的。另外，最长公共子序列不一定只有一个，而我们需要寻找的是其中一个。当然，如果要求子序列里面的元素必须连成一片也是可以的。实际上，连成一片的版本比这里实现的更容易。过程我们可以通过蛮力策略解决这个问题，步骤如下：.检查S11.m里面每一个子序列。.看看其是否也是S21.n里的子序列。.在每一步记录当前找到的子序列里面最长的子序列。这种方法的效率十分低下。因此本实验采用动态规划的方法实现该算法。利用动态规划寻找最长公共子序列步骤如下：寻找最长公共子序列的长度。扩展寻找长度的算法来获取最长公共子序列。策略：考虑序列S1和S2的前缀序列。设ci,j=|LCS(S1

3、1.i,S21.j)|，则有cm，n=|LCS(S1，S2)|所以有-ci1,j1+1,如要S1i=S2jci，j=-maxci-1,j,ci,j-1,如果5邛752口然后回溯输出最长公共子序列过程：实现源代码packagelcsimple;publicclassLCSImplem/返回一个决定搜索方向的数组privatestaticintgetLength(charstringArr1,charstringArr12)intb=newintstringArr1.lengthstringArr12.length;intc=newintstringArr1.lengthstringArr12.l

4、ength;for(inti=1;istringArr1.length;i+)for(intj=1;j=cij-1)cij=ci-1j;bij=0;/S1i#S2j的情况elsecij=cij-1;bij=-1;returnb;/回溯的实现，采用递归法privatestaticvoidDisplay(intb,charstringArr1,inti,intj)if(i=0|j=0)return;if(bij=1)Display(b,stringArr1,i-1,j-1);System.out.print(stringArr1i+);elseif(bij=0)Display(b,stringAr

5、r1,i-1,j);elseif(bij=-1)Display(b,stringArr1,i,j-1);publicstaticvoidmain(Stringargs)Stringstr1=ABCBDAB;Stringstr2=BDCABA;str1=+str1;str2=+str2;charstringArr1=str1.toCharArray();charstringArr2=str2.toCharArray();intb=getLength(stringArr1,stringArr2);Display(b,stringArr1,stringArr1.length-1,stringArr2

6、.length-1);断点调试及代码分析首先在main方法里定义两个字符串，如：Stringstri-ABCEDAB;Stringstr2=*B-DCABAT,;对这两个字符串，使它们的第一个字符为空，即初始化之后的c口口的第一行第一列，之所以要空出，是因为C口口代表的是两个字符串数组多少个，0的意思就是某个字符串的长度为0。然后将这两个字符串分割为char型数组：tri=十str1;tr2=T,T,4str2;ohaxstringArrl=str1.icharEstringArr2=str2.toChsrArray();接下来就调用getLength方法计算出决定搜索方向的数组，传到该方法的

7、两个数组参数stringArr1和stringArr2的值可以看到Name“sEringAirrtValue(id=16)A0AAaaEA司C*4EA5D*AA7EVQStringArrl2(ic=17)x0：1BA.2DA3CAMAA：5BA6A然后定义两个二维数组b，c，大小为stringArr1.length*stringArr12.length，用于接受结果矩阵。intb=newintstringArrl.IsngthstringAc=newintstringAril.lengthstrin.g?krrl2_length.接着遍历每一个stringArrl

8、的值，与stringArr2的每一个值做比较：far(inti=1;tringArrl.lengtli;i+)far(intj=1;j=cij-lBcij=口i-1jib5j=0;1sl口的舐elsej=cij-1;bijl=-1；的值为1,不匹配时，就对C矩阵做出比较，该值在矩阵中左边的数值大于上边的数值时，b矩阵在当前位置在字符匹配时的值为0，反之记为-1。因此，计算返回b矩阵，输出b矩阵fornti=0;ib.length;i44)-for(iritj=0;jDisplay(brstringArrlji-ljj-1);system.out.prim；(stringArrli+m);els

9、ei-E(3.j=0)-；Dis-play(brstringArrl,i-1,jj;Li-if(hlj=一二).：Disp2ay(brstringArr1j一1)j当当前值为1时，说明字符匹配成功，再对左上方的值进行比较；当当前值为0时，说明左边的值大于上边的值，采用递归法，再对上边的值进行比较；当当前值为-1时，对左边的值进行比较。下面是return;System,out.println(士+”=+j);ifbij1=1)0上b口工与yfb.strincrArrlri-11H-1;晚Marker?;匚Properties泉Setverz胸DataSourceExplorer治snippets

10、QCansoleLCSImplemJavaApplicationD:jdk_1816上_1Hliinjauawr.eKe(ECKlT年12月5日7=66=65=54=B3=43=32=2=:这个方法，就是对下面矩阵方向的计算：最后输出判断中匹配上的结果。00这个方法，就是对下面矩阵方向的计算：最后输出判断中匹配上的结果。000Q0000TJJ10i一工t上20TTJ?:0TT一30T0TrQt算法分析由于每次调用至少向上或向左(或向上向左同时)移动一步，故最多调用(m*n)次就会遇到i=。或j=0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为。(m*n)。实验结

11、果在main方法中输入的字符串为：JJ-L_LJY2J-J1XLOJL工J.QJLJLJ.Stringstrl=T,ABCBDABTI;S-trinq-S-tr2=T,BDCABAT,;所以得到结果：termmated：BCBA改变输入的字符串测试：上JJILB_JnJCLJVU-J.ILLULd1JI7Lu-Jl.XX|_J口J-fStringstrl=TlABCBDABEFEVr,;Stringstr2=BDCABAEFTGf;I*MarkersEProperties鼎ServersDataSourceEjcplore-r趋Snippe=：terminated?-LCSImplemJavaApplicationD:jdlc1.9jdk1.9binjavaw.exeBCBAEF