lcsuseo2mmem.java

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

/*
 * 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
 */
//19 Feb 2008
package cn.edu.whu.iss.algorithm.unit15.lcs;

public class LCSUseO2mMem extends AbstractLCS {
	
	protected int[][] c;
	
	public LCSUseO2mMem(){
		super();
	}
	
	public LCSUseO2mMem(String x,String y){
		super(x,y);
	}

	public int lcsLength() {
		int m = x.length();
		int n = y.length();
		c = new int[2][m];
		int now = 0;
		for(int k=0;k<m;k++){
			c[now][k]  = 0;
		}
		int j = 0;
		while(j<n){
			now = 1-now;
			int i = 0;
			if(x.charAt(i)==y.charAt(j)){
				c[now][i] = 1;
				b[i][j] = SKEW;
			}else if(c[1-now][i]>=0){
				c[now][i] = c[1-now][i];
				b[i][j] = LEFT;
			}else{
				c[now][i] = 0;
				b[i][j] = UP;
			}
			for(i=1;i<m;i++){
				if(x.charAt(i)==y.charAt(j)){
					c[now][i] = c[1-now][i-1]+1;
					b[i][j] = SKEW;
				}else if(c[1-now][i]>=c[now][i-1]){
					c[now][i] = c[1-now][i];
					b[i][j] = LEFT;
				}else{
					c[now][i] = c[now][i-1];
					b[i][j] = UP;
				}
			}
			j++;
		}
		return c[now][m-1];
	}

}