compromise.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.*;

/**
 * 
 */

/**
 * ID:2250
 * DP
 * @author yhm
 *
 */
public class Compromise {
	static String[] text1;
	static String[] text2;
	static StringBuffer buffer;
	static int[][] length;
	static int[][] mark;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			ArrayList<String> list1 = new ArrayList<String>();
			while(cin.hasNext()){
				String str = cin.next();
				if(str.equals("#")){
					break;
				}
				list1.add(str);
			}
			ArrayList<String> list2 = new ArrayList<String>();
			while(cin.hasNext()){
				String str = cin.next();
				if(str.equals("#")){
					break;
				}
				list2.add(str);
			}
			
			text1 = list1.toArray(new String[0]);
			text2 = list2.toArray(new String[0]);
			solve();
			
		}
		

	}
	
	
	static void solve(){
		int len1 = text1.length;
		int len2 = text2.length;
		length = new int[len1+1][len2+1];
		mark = new int[len1+1][len2+1];
		
		for(int i=1;i<=len1;i++){
			for(int j=1;j<=len2;j++){
				if(text1[i-1].equals(text2[j-1])){
					length[i][j] = length[i-1][j-1]+1;
					mark[i][j] = 1;
				}
				else{
					if(length[i-1][j]>length[i][j-1]){
						length[i][j] = length[i-1][j];
						mark[i][j] = 2;
					}
					else{
						length[i][j] = length[i][j-1];
						mark[i][j] = 3;
					}
				}
			}
		}
		
		buffer = new StringBuffer();
		print(len1,len2);
		System.out.println(buffer);
		
	}
	

	static void print(int i, int j){
		if(i==0 || j==0){
			return;
		}
		if(mark[i][j]==1){
			print(i-1,j-1);
			buffer.append(text1[i-1]+" ");
		}
		else if(mark[i][j]==2){
			print(i-1,j);
		}
		else{
			print(i,j-1);
		}
	}
	

}