字符串最大公共子序列以及最大公共子串问题
最大公共子序列
public static void lcs2(){ String x="abcdepoi"; String y="bcdefpoi"; int substringLength1 = x.length(); int substringLength2 = y.length(); int opt[][]=new int [substringLength1+1][substringLength2+1]; for(int i=1;i<=substringLength1;i++) for(int j=1;j<=substringLength2;j++) { if(x.charAt(i-1)==y.charAt(j-1)) opt[i][j]=opt[i-1][j-1]+1;//状态转移方程， } int max=opt[0][0]; int m=0,n=0; for(int i=substringLength1;i>=1;i--) for(int j=substringLength2;j>=1;j--){ if(opt[i][j]>max) { max=opt[i][j]; m=i; n=j; } } System.out.println("x = "+x); System.out.println("y = "+y); System.out.println("max = "+max); StringBuffer sb=new StringBuffer(); for(int i=m,j=n;i>=1&&j>=1;i--,j--) { if(opt[i][j]>0) sb.append(x.charAt(i-1)); } String result=sb.toString(); for(int i=result.length()-1;i>=0;i--) System.out.print(result.charAt(i)); }