最长公共子序列问题

实验三最长公共子序列问题.实验环境本实验采用java语言编写实现，环境：JDK1.8,编译器：eclipse.实验目的通过最长公共子序列问题，巩固并详细分析动态规划思想和解题步骤。.设计思路最长公共子序列的定义为：设有两个序列SJ1..m］和S2［1..n］，需要寻找它们之间的一个最长公共子序列。例如，假定有两个序列：SJINTHEBEGINNINGS2：ALLTHINGSARELOST则务和马的一个最长公共子序列为THING。又比如：S1：ABCBDABS2：BDCABA则它们的一个最长公共子序列为BCBA。这里需要注意的是，一个子序列不一定必须是连续的，即中间可被其他字符分开，单它们的顺序必须是正确的。另外，最长公共子序列不一定只有一个，而我们需要寻找的是其中一个。Word文档当然，如果要求子序列里面的元素必须连成一片也是可以的。实际上，连成一片的版本比这里实现的更容易。4.过程我们可以通过蛮力策略解决这个问题，步骤如下：.检查S1[1..m]里面每一个子序列。.看看其是否也是S2[1..n]里的子序列。.在每一步记录当前找到的子序列里面最长的子序列。这种方法的效率十分低下。因此本实验采用动态规划的方法实现该算法。利用动态规划寻找最长公共子序列步骤如下：.寻找最长公共子序列的长度。.扩展寻找长度的算法来获取最长公共子序列。策略：考虑序列S1和S2的前缀序列。设c[i，j]=|LCS(S1[1..i],S2[1..j])|，则有c[m，n]=|LCS(S1，S2)|所以有「c[i-1,j-1]+1, 如要S1[i]=S2[j]c[i，j]="max{c[i-1,j],c[i,j-1]}, 如果5邛]752口]然后回溯输出最长公共子序列过程：Word文档、5.实现源代码packageIcsimple;publicclassLCSImplem{//返回一个决定搜索方向的数组privatestaticint[][]getLength(char[]stringArrl,char[]stringArr12){int[][]b=newint[stringArr1.length][stringArr12.length];int[][]c=newint[stringArr1.length][stringArr12.length];for(inti=1;i<stringArr1.length;i++){for(intj=1;j<stringArr12.length;j++){//S1[i]=S2[j]的情况if(stringArr1[i]==stringArr12[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}//S1[i]#S2[j]的情况Word文档elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=0;}//S1[i]#S2[j]的情况else{c[i][j]=c[i][j-1];b[i][j]=-1；}}}returnb;}//回溯的实现，采用递归法privatestaticvoidDisplay(int[][]b,char[]stringArr1,inti,intj){if(i==0||j==0)return;if(b[i][j]==1){Display(b,stringArr1,i-1,j-1);System.out.print(stringArr1[i]+"");}elseif(b[i][j]==0){Display(b,stringArr1,i-1,j);}elseif(b[i][j]==-1){Display(b,stringArr1,i,j-1);}}publicstaticvoidmain(String[]args){Stringstr1="ABCBDAB";Stringstr2="BDCABA";str1=""+str1;str2=""+str2;char[]stringArr1=str1.toCharArray();char[]stringArr2=str2.toCharArray();int[][]b=getLength(stringArr1,stringArr2);Word文档Display(b,stringArrl,stringArrl.length-1,stringArr2.length-1);}}6,断点调试及代码分析首先在main方法里定义两个字符串，如：Stringstri=nABCBDAB1';Stringstr2=*'B-DCABAT,;对这两个字符串，使它们的第一个字符为空，即初始化之后的c[][]的第一行第一列，之所以要空出，是因为c□□代表的是两个字符串数组多少个，0的意思就是某个字符串的长度为0。然后将这两个字符串分割为char型数组：stri=""+str1;str2=T,T,4str2;ohax[]□tringArr1=str1.taChar^rray(iclia.r[]stringArr2=str2.tcCharArray(];接下来就调用getLength方法计算出决定搜索方向的数组，传到该方法的两个数组参数stringArr1和stringArr2的值可以看到Word文档Name“OstringArr1Value(id-16)A[0]A：1]AaaBA司C*：4]B上：5]D*[6]AA[7]EvQstringArr12(ic=17)A[0]上J]BA2JDA-31Cx⑷AA：5]EA[6]A然后定义两个二维数组b[][],c[][],大小为stringArr1.length*stringArr12.length,用于接受结果矩阵。int[][]b=newint[stringArr1.length]'stringArrl2.length.]int[][]c-newint[stringArr1.length][stringArrl2-length.]接着遍历每一个stringArr1的值,与stringArr2的每一个值做比较：±or(inti=l;i<stringArr1.lengtli;=++】｛for(intj=1;j<3tringArr12.length;j++)■[/rfm-1r■"B cC「'"1b-l-iI—I循环的第一层判断，就是当当前字符匹配的时候，c[i][j]最为前缀序列为后面的匹配计算使用，将当前值赋值为1，b[i][j]用于保存匹配结果记为1：=£2[:j]的情况if(stringArrl[i]==stringArr12[j])■[c[i][j]= [j-1]+1;b[i][j]=1:把下面的两个判断作为第二层判断，即当当前字符不匹配的时候对C[i][j]做计算，C[i][j]就是该值在矩阵中上面一个数和左边一个数中较大的值：Word文档

//Sl[i]/S2[口]的情况elseif(cEi-1][j]>=c[i][j-lB]c[i][j]=u[1-1][j]i上[3][j]=0；口]的情况//SI[ielse{口]的情况e[上[这些判断就是对该矩阵值的计算，c矩阵:/ 0 1 2 / 0 1 2 3 4 5 60但是这个方法返回的是b矩阵，b矩阵在当前位置在字符匹配时的值为1,不匹配时，就对c矩阵做出比较，该值在矩阵中左边的数值大于上边的数值时，b矩阵在当前位置在字符匹配时的值为0，反之记为-1。因此，计算返回b矩阵，输出b矩阵for{±nti=0;i<b.length;i-l-4J-[for(intj=0;j<ij[i].length;j+-F]-[System.out.print((b[i][j]]+lp 11);System.-out.printIn(];得到：Word文档

oa□oTOC\o"1-5"\h\z0 1-11-10 1-11-10 00ai-1Cacc01c10010最后就是对结果的输出，对b矩阵调用Display方法:Display(b,stringArrl,string'Arr1.len.gth-1,stringArr2.len.gth.-l)『『回过的匚ik1用艺门云privatestatiovoid」j.Ep_zi¥〔int：][]b,ohaj[]strlngArrl,int二1intj]{ifi：i一:■II--刁retiirt.;LE-[]匚]—1){(jzir2trinjArrl,i-1,j'L);tGjn. 二tistrtn1岂--71 ;hIshLf(■：.[,.][j]一一0)-：Ptsp.ayilir-= :ngArr't''r~llMGif(h[L][j]—一二)<Display(brstringArr1, j-1)当当前值为1时，说明字符匹配成功，再对左上方的值进行比较;当当前值为0时，说明左边的值大于上边的值，采用递归法，再对上边的值进行比较；当当前值为-1时，对左边的值进行比较。下面是对b的迭代:p5 return;System,out.prim；ln(i+r,=>Fr+-i);i±lb(i](t)--){DisolavfbrstrincrArrl<i-1rH-11;融Markers二PropertiesSetversDataSourceExplore-sniopetsQCohedI?<termin3ted>LCSIrnplern[JavaApplication]D!\jdk_l •fllhinMauaMr.ewe(2£rtT年12月5日7-->66——>6Word文档

这个方法，就是对下面矩阵方向的计算:最后输出判断中匹配上的结果。0()这个方法，就是对下面矩阵方向的计算:最后输出判断中匹配上的结果。0()o°000QtTt—10\一1-itV-20TT一2；0Tt一30TT()Tr0\tJ7.算法分析由于每次调用至少向上或向左(或向上向左同时)移动一步，故最多调用(m*n)次就会遇到i=0或j=0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为。(m*n)。Word文档

8.实验结果在main方法中输入的字符串为：_LU- VLJ_LClIIAUJ_IJL*Q」J_JLJ：String-strl=T,7YBCBDABTI;S-trinq-S-tr2-T,BDCABATF;所以得到结果：<termmated：BCBA改变输入的字符串测试：jj1ULUJ__LnJCLJV3,JILLCL^L111LrJLULJ.|_J0J—9・String占七二1=TlABCBDABEFEVr,;Stringstr2=『'日DCABAEFCgI";I*Markers二Properties鼎Servers理OatsSourceE)cplore-r趋Snippe■=；termina