Java最长公共子序列示例源码

java;">package com.wsy.dynamic;import java.util.HashMap;import java.util.Map;public class ImpLCS { public String getLCS(String str1, String str2, int n, int m){  validate(str1, str2);  char[] a = str1.toCharArray();  char[] b = str2.toCharArray();  int[][] c = new int[n+1][m+1];  //存放序列  Map<String,String> map = new HashMap<String,String>();  //初始化参数  for(int i = 0;i<=n;i++){   c[i][0] = 0;   map.put(i + "0", "");  }  for(int i = 0;i<=m;i++){   c[0][m] = 0;   map.put("0" + i, "");  }  for(int i = 1;i<=n;i++){   for(int j = 1;j<=m;j++){    if(a[i-1] == b[j-1]){     c[i][j] = c[i-1][j-1] + 1;     String tmp = 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];      String tmp = map.get(changeNum(i,j-1));      map.put(changeNum(i,j), tmp);     }else{      c[i][j] = c[i-1][j];      String tmp = map.get(changeNum(i-1,j));      map.put(changeNum(i,j), tmp);     }    }   }  }  String key = changeNum(n,m);  return map.get(key); } /**  * 将数字拼接成字符串  * @param i  * @param j  * @return  */ private String changeNum(int i, int j) {  StringBuilder sb = new StringBuilder(String.valueOf(i));  return sb.append(j).toString(); } /**  * 验证参数  * @param str1  * @param str2  */ private void validate(String str1, String str2) {  // 略 } public static void main(String[] args) {  ImpLCS lcs = new ImpLCS();  String rs = lcs.getLCS("12345", "12334", 5, 4);  System.out.println("---:" + rs); }}