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);
}
}
总结
以上是本文的全部内容，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持！