lcs.java

《算法设计与分析》王晓东编著

import java.util.*;
public class Lcs {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		System.out.print("Please input the length of string x:");
		int xl = in.nextInt();
		System.out.print("Please input string x:");
		String strA = in.next();
		System.out.print("Please input the length of string y:");
		int yl = in.nextInt();
		System.out.print("Please input string y:");
		String strB = in.next();
		char[] x = new char[xl];
		char[] y = new char[yl];
		for(int i=0;i<xl;i++)
			x[i] = strA.charAt(i);
		for(int i=0;i<yl;i++)
			y[i] = strB.charAt(i);
		int[][] lcsTable = new int[xl+1][yl+1];
		int[][] direct = new int[xl+1][yl+1];
		lcsLength(x,y,lcsTable,direct);
		for(int i=1;i<=xl;i++){
			for(int j=1;j<=yl;j++)
				System.out.print(lcsTable[i][j]+"\t");
			System.out.println();
		}
		lcs(xl,yl,x,direct);
	}
	public static int lcsLength(char[] x,char[] y,int[][] lcsTable,int[][] direct){
		int m = x.length;
		int n = y.length;
		for(int i=0;i<=m;i++)
			lcsTable[i][0] = 0;
		for(int i=1;i<=n;i++)
			lcsTable[0][i] = 0;
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++){
				if(x[i-1]==y[j-1]) {lcsTable[i][j]=lcsTable[i-1][j-1]+1;direct[i][j] = 1;}
				else 
					if(lcsTable[i-1][j]>lcsTable[i][j-1]){
						lcsTable[i][j] = lcsTable[i-1][j];
						direct[i][j] = 2;
						}
				else
				{	lcsTable[i][j] = lcsTable[i][j-1];direct[i][j] = 3;}
		}
		return lcsTable[m][n];
	}
	public static void lcs(int i,int j,char[] x,int[][] direct){
		if(i==0 || j==0) return;
		if(direct[i][j]==1){
			lcs(i-1,j-1,x,direct);
			System.out.print(x[i-1]);
		}
		else if(direct[i][j]==2) lcs(i-1,j,x,direct);
		else lcs(i,j-1,x,direct);
	}
	
}