lcsuseommem.java

<算法导论>第二版大部分算法实现. 1. 各类排序和顺序统计学相关 2. 数据结构 2.1 基本数据结构 2.2 散列表 2.3 二叉查找树 2.4 红黑树 2.5 数据结构

/*
 * 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;

import java.util.Arrays;

public class LCSUseOmMem extends AbstractLCS {

	protected int[] c;
	
	public LCSUseOmMem(){
		super();
	}
	
	public LCSUseOmMem(String x,String y){
		super(x,y);
	}
	
	public int lcsLength() {
		int m = x.length();
		int n = y.length();
		c = new int[m];
		Arrays.fill(c, 0);
		int b = 0;
		int j = 0;
		while(j<n){
			int i = 0;
			int a = 0;
			b = c[i];
			if(x.charAt(i)==y.charAt(j)){
				c[i] = 1+a;
				super.b[i][j] = SKEW;
			}else if(0>=b){
				c[i] = 0;
				super.b[i][j] = UP;
			}else{
				c[i] = b;
				super.b[i][j] = LEFT;
			}
			for(i=1;i<m;i++){
				a = b;
				b = c[i];
				if(x.charAt(i)==y.charAt(j)){
					c[i] = 1+a;
					super.b[i][j] = SKEW;
				}else if(c[i-1]>=b){
					c[i] = c[i-1];
					super.b[i][j] = UP;
				}else {
					c[i] = b;
					super.b[i][j] = LEFT;
				}
			}
			j++;
		}
		return c[m-1];
	}

}