Java最长公共子序列示例源码
最长公共子序列(LongestCommonSubsequence)定义:两个或多个已知数列的子序列集合中最长的就是最长公共子序列。其实说到最长公共子序列,还有一个要提到的是最长公共子串(LongestCommonSubstring),它指的是两个字符串中的最长公共子串,要求子串一定连续。关于最长公共子串的内容我们后续也会讲到,今天先来看下最长公共子序列的相关内容。
之前看过一个LCS算法的实现过程,觉得太过繁琐。自己写了一个比较简单的,此处仅仅介绍实现过程。
程序代码测试通过,需要的童鞋可以在这里拷贝一下,代码如下:
packagecom.wsy.dynamic; importjava.util.HashMap; importjava.util.Map; publicclassImpLCS{ publicStringgetLCS(Stringstr1,Stringstr2,intn,intm){ validate(str1,str2); char[]a=str1.toCharArray(); char[]b=str2.toCharArray(); int[][]c=newint[n+1][m+1]; //存放序列 Mapmap=newHashMap (); //初始化参数 for(inti=0;i<=n;i++){ c[i][0]=0; map.put(i+"0",""); } for(inti=0;i<=m;i++){ c[0][m]=0; map.put("0"+i,""); } for(inti=1;i<=n;i++){ for(intj=1;j<=m;j++){ if(a[i-1]==b[j-1]){ c[i][j]=c[i-1][j-1]+1; Stringtmp=map.get(changeNum(i-1,j-1)); map.put(changeNum(i,j),tmp+String.valueOf(a[i-1])); }else{ if(c[i][j-1]>c[i-1][j]){ c[i][j]=c[i][j-1]; Stringtmp=map.get(changeNum(i,j-1)); map.put(changeNum(i,j),tmp); }else{ c[i][j]=c[i-1][j]; Stringtmp=map.get(changeNum(i-1,j)); map.put(changeNum(i,j),tmp); } } } } Stringkey=changeNum(n,m); returnmap.get(key); } /** *将数字拼接成字符串 *@parami *@paramj *@return */ privateStringchangeNum(inti,intj){ StringBuildersb=newStringBuilder(String.valueOf(i)); returnsb.append(j).toString(); } /** *验证参数 *@paramstr1 *@paramstr2 */ privatevoidvalidate(Stringstr1,Stringstr2){ //略 } publicstaticvoidmain(String[]args){ ImpLCSlcs=newImpLCS(); Stringrs=lcs.getLCS("12345","12334",5,4); System.out.println("---:"+rs); } }
总结
以上是本文的全部内容,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持!