Simone最长公共子序列的JAVA JAV分析LCS
的有关信息介绍如下：
最长公共子序列的问题常用于解决字符串的相似度，是一个非常实用的算法，作为码农，此算法是我们的必备基本功。最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。
问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列
方案<1> 枚举法
这种方法是最简单，也是最容易想到的，当然时间复杂度也是龟速的，一个长度为N的字符串，其子序列有2^N个，每个子序列要在第二个长度为N的字符串中去匹配，匹配一次需要O(N)的时间，总共也就是O(N*2^N)，可以看出，时间复杂度为指数级，恐怖的令人窒息。
方案<2> 动态规划:
这里我们采用的是矩阵实现，也就是二维数组。
第一步：先计算最长公共子序列的长度。
第二步：根据长度，然后通过回溯求出最长公共子序列。
注意：动态规划的一个重要性质特点就是解决“子问题重叠”的场景，可以有效的避免重复计算，根据上面的公式其实可以发现C[i,j]一直保存着当前(Xi,Yi)的最大子序列长度。
求解LCS长度辅助表C
递归输出字符：
功能程序源代码：
package ch3.dynamic.algorithm;
public class LCS {
////construct thetable of state
/***
* *
* 这一部分我们使用辅助表，从左上角开始计算每一个位置上LCS的长度
* 判断算法：
*/
public static int[][] lcsLength(Object[] x,Object[] y){
int m=x.length;
int n=y.length;
int[][] c = new int[m+1][n+1];
int i,j;
for(i=1;i<=m;i++){
c[i]=0;
}
for(j=0;j<=n;j++){
c[j]=0;
}
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
if(x[i-1].equals(y[j-1])){
c[i][j]=c[i-1][j-1]+1;
}else if(c[i-1][j]>=c[i][j-1]){
c[i][j]=c[i-1][j];
}else{
c[i][j]=c[i][j-1];
}
}
}
return c;
}
/////print the lcs
////采用递归的方式将结果打印出来
public static void printLcs(int[][] c,Object[] x,Object[] y,int i,int j){
if(i==0||j==0){
return ;
}
if(x[i-1].equals(y[j-1])){
printLcs(c,x,y,i-1,j-1);
System.out.print(x[i-1]+" ");
}else if(c[i-1][j]>=c[i][j-1]){
printLcs(c, x, y, i-1, j);
}else{
printLcs(c, x, y, i, j-1);
}
}
}
