阳江网站建设公司/网站如何推广出去

公共子序列不同于公共子串，如“hello”与“hleeo”
最大公共子序列为：heo （不要求连续）
最大公共子串为：h
对过程不好理解的，推荐看一下这个：远洋号
代码如下：

public class Run {public static void main(String[] args) throws InterruptedException {//两个测试串String s1 = "hello";String s2 = "hleeo";System.out.println(new Run().maxPubLength(s1, s2));}public int maxPubLength(String s1,String s2) {//LinkedList保存公共子序列的字符LinkedList<Character> list = new LinkedList();//二维数组res保存每一步的状态int [][] res = new int[s1.length()+1][s2.length()+1];int m = s1.length();int n = s2.length();//求最大公共子序列长度for(int i=0;i<=m;i++) {for(int j = 0;j<=n;j++) {if(i==0||j==0) res[i][j]=0;else if(s1.charAt(i-1)==s2.charAt(j-1)) {res[i][j] = res[i-1][j-1]+1;	}else res[i][j]=Math.max(res[i-1][j], res[i][j-1]);}}//统计公共子序列包含的字符int i = m;int j = n;while(i>=1&&j>=1){if(s1.charAt(i-1)==s2.charAt(j-1)) {list.add(s1.charAt(i-1));i--;j--;}else {if(i ==1) j--;else  i--;}}//采用直接输出形式Collections.reverse(list);for(Character c:list) {System.out.println(c);}return res[m][n];}}

运行结果

h
e
o
3