abstractlcs.java

来自「<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关」· Java 代码 · 共 74 行

/*
 * Copyright (C) 2003-2008 Wang Pengcheng <[e-mail]>
 * Permission is granted to copy, distribute and/or modify this
 * document under the terms of the GNU Free Documentation License,
 * Version 2.0 or any later version published by the Free Software Foundation;
 * with no Invariant Sections.
 * You may obtain a copy of the License at
 *   http://www.gnu.org/licenses/lgpl.txt
 */
//18 Feb 2008
package cn.edu.whu.iss.algorithm.unit15.lcs;

public abstract class AbstractLCS implements GetLCSInfor{
	
	protected static final short UP = 1,LEFT =2,SKEW =3;
	
	protected short[][] b;
	
	protected String x,y;
	
	private int l;
	
	public AbstractLCS(){
		this.x = "";
		this.y = "";
		b = new short[x.length()][y.length()];
	}
	
	public AbstractLCS(String x,String y){
		this.x = x;
		this.y = y ;
		b = new short[x.length()][y.length()];
	}
	
	public String getLCS(String x, String y) {
		this.x = x;
		this.y = y;
		b = new short[x.length()][y.length()];
		return getLCS();
	}
	
	public String getLCS() {
		l = lcsLength();
		int k=0;
		String ans = ">";
		int i = x.length() -1,j = y.length() -1;
		while(i>=0&&j>=0){
			if(b[i][j]==SKEW){
				ans = x.charAt(i)+ans;
				k++;
				if(k<l){
					ans=","+ans;
				}
				i--;
				j--;
			}else if(b[i][j]==UP){
				i--;
			}else{
				j--;
			}
		}
		ans="<"+ans;
		return ans;
	}

	public int lcsLength(String x, String y) {
		this.x = x;
		this.y = y;
		b = new short[x.length()][y.length()];
		return lcsLength();
	}
	
}