simplelcs.java

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

/*
 * 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 class SimpleLCS extends AbstractLCS {
	private static short LABEL = -1;
	
	protected int[][] c;
	
	public SimpleLCS(){
		super();
	}

	public SimpleLCS(String x,String y){
		super(x,y);
	}

	public int lcsLength() {
		int m = x.length();
		int n = y.length();
		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(x.charAt(i-1)==y.charAt(j-1)){
					c[i][j] = c[i-1][j-1]+1;
					b[i-1][j-1] = SKEW;
				}else if(c[i-1][j]>=c[i][j-1]){
					c[i][j] = c[i-1][j];
					b[i-1][j-1] = UP;
				}else{
					c[i][j] = c[i][j-1];
					b[i-1][j-1] = LEFT;
				}
			}
		return c[m][n];
	}
	
	public int lcsLengthUseMem(){
		int m = x.length();
		int n = y.length();
		c = new int[m+1][n+1];
		b = new short[m][n];
		for(int i=0;i<=m;i++)
			for(int j=0;j<=n;j++){
				c[i][j] = LABEL;
			}
		return lookupLCS(m, n);
	}
	
	private int lookupLCS(int i,int j){
		if(c[i][j]!=LABEL){
			return c[i][j];
		}
		if(i==0||j==0){
			return 0;
		}
		if(x.charAt(i-1)==y.charAt(j-1)){
			b[i-1][j-1] = SKEW;
			return lookupLCS(i-1, j-1)+1;
		}else {
			int p = lookupLCS(i-1, j);
			int q = lookupLCS(i, j-1);
			if(p>=q){
				b[i-1][j-1] = UP;
				return p;
			}else{
				b[i-1][j-1] = LEFT;
				return q;
			}
		}
	}
	
	public String getLCSWithoutB(){
		String s = ">";
		int l = c[x.length()][y.length()];
		int k =0;
		int i = x.length();
		int j = y.length();
		while(i>0&&j>0){
			if(x.charAt(i-1)==y.charAt(j-1)){
				k++;
				s = x.charAt(i-1)+s;
				if(k<l){
					s = ","+s;
				}
				i--;
				j--;
			}else if(i>1){
				if(c[i-1][j]==c[i][j]){
					i--;
				}else{
					j--;
				}
			}else if(j>1){
				if(c[i][j-1]==c[i][j]){
					j--;
				}else{
					i--;
				}
			}else {
				break;
			}
		}
		return "<"+s;
	}

}