最长公共子序列求解
package longsequence;
import java.util.Scanner;
public class Long_sequence {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
System.out.println("此程序用来求最长子序列问题：\n"+"请输入两个字符串");
String str1,str2;
System.out.print("str1= ");
str1=input.next();
System.out.print("str2= ");
str2=input.next();
char a[]=str1.toCharArray();
char b[]=str2.toCharArray();
//char m=input.next().charAt(0);
System.out.println("由以上填充数组可见，匹配的最长序列length= "+Lsequence(a,b));
}
static int Lsequence(char a[],char b[]) {
int c[][]=new int[a.length+1][b.length+1];
for(int i=0;i<a.length+1;i++) {
for(int j=0;j<b.length+1;j++) {
if(i==0||j==0) {
c[i][j]=0;
}
else if(i>0&&j>0&&a[i-1]==b[j-1]) {
c[i][j]=c[i-1][j-1]+1;
}
else if(i>0&&j>0&&a[i-1]!=b[j-1]) {
c[i][j]=max(c[i][j-1],c[i-1][j]);
}
}
}
for(int i=0;i<a.length+1;i++) {
for(int j=0;j<b.length+1;j++) {
System.out.print(c[i][j]+" ");
}
System.out.println();
}
return c[a.length][b.length];
}
static int max (int a,int b) {
if(a>b)return a;
else return b;
}
}
