最长公共子序列

import java.util.Scanner;

public class Main {


static int b[][];//此数组用于计算最长公共子序列中每个字符时怎么样得到的

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String str1=sc.nextLine();
String str2 =sc.nextLine();
b=new int[str1.length()+1][str2.length()+1];

System.out.println(lcsLength(str1,str2,b));
lcs(str1.length(),str2.length(),str1,b);

}
//关于此问题，需要递归公式,c[i][j]记录序列Xi和yj的最长
//公共子序列的长度，当i=0或j=0时，空序列是两个字符串的最长
//公共子序列，故此时c[i][j]=0
//当Xi=yi时，c[i][j]=c[i-1][j-1]+1；
//else max{c[i][j-1],c[i-1][j]}
public static int lcsLength(String str1,String str2,int [][]b)
{
int m=str1.length();
int n=str2.length();
int c[][]=new int[m+1][n+1];
for(int i=1;i<=m;i++)
c[i][0]=0;
for(int i=1;i<=n;i++)
c[0][i]=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
if(str1.charAt(i-1)==str2.charAt(j-1))
{
c[i][j]=c[i-1][j-1]+1;
b[i][j]=1;
}
else if(c[i-1][j]>=c[i][j-1])
{
c[i][j]=c[i-1][j];
b[i][j]=2;
}
else
{
c[i][j]=c[i][j-1];
b[i][j]=3;
}

}
return c[m][n];
}
//构造最长公共子序列
public static void lcs(int i,int j,String str,int b[][])
{
if(i==0||j==0)
return;
if(b[i][j]==1)
{
lcs(i-1,j-1,str,b);
System.out.print(str.charAt(i-1));
}
else if(b[i][j]==2)
lcs(i-1,j,str,b);
else
lcs(i,j-1,str,b);

}
}




下面由我来进一步解释一下最长公共子序列问题的解法，当然，这不是我发明的，从书上学来的。
最长公共子序列问题具有最优子结构性质。
设序列X={x1,x2,...,xm},Y={y1,y2,...,yn}的最长公共子序列是Z={z1,z2,...zk},则
(1)如果xm=yn,则zk=xm=yn,且Zk-1是Xm-1和Yn-1的最长公共子序列
(2)else if(zk不等于xm),则Z是Xm-1和Y的最长公共子序列
(3)else if(zk不等于yn),则Z是X和Yn-1的最长公共子序列
由此德奥递推公式
公共子序列，故此时c[i][j]=0  i=0 or j=0
当Xi=yi时，c[i][j]=c[i-1][j-1]+1；
else max{c[i][j-1],c[i-1][j]}

用数组b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的，在构造最长公共子序列时用到了。
在构造最长公共子序列时，首先从b[m][n]开始，依其值在数组b中搜索，当b[i][j]=1,表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列尾部加上xi得到的序列。当b[i][j]=2时，表示Xi和Yj的最长公共子序列是由Xi-1和Yj的最长公共子序列相同，当b[i][j]=3时，表示Xi和Yj的最长公共子序列是由Xi和Yj-1的最长公共子序列相同，由此可找出最长公共子序列的具体内容。