【最长公共子序列】

在两个字符串中，有些字符会一样，可以形成的子序列也有可能相等，因此，长度最长的相等子序列便是两者间的最长公共字序列。例如序列X=''ABCBDAB''与序列Y =''BDCABA''，最长公共子序列为“BCDA”.

基本概念：

子序列(subsequence)：一个特定序列的子序列就是将给定序列中零个或多个元素去掉后得到的结果(不改变元素间相对次序)。例如序列<A,B,C,B,D,A,B>的子序列有：<A,B>、<B,C,A>、<A,B,C,D,A>等。

公共子序列(common subsequence)：给定序列X和Y，序列Z是X的子序列，也是Y的子序列，则Z是X和Y的公共子序列。例如X=[A,B,C,B,D,A,B]，Y=[B,D,C,A,B,A[，那么序列Z=[B,C,A]为X和Y的公共子序列，其长度为3。但Z不是X和Y的最长公共子序列，而序列[B,C,B,A]和[B,D,A,B]也均为X和Y的最长公共子序列，长度为4，而X和Y不存在长度大于等于5的公共子序列。对于序列[A,B,C]和序列[E,F,G]的公共子序列只有空序列[]。

最长公共子序列：给定序列X和Y，从它们的所有公共子序列中选出长度最长的那一个或几个。

通常求公共子序列有三种方法：穷举法、备忘录法、自底向上法。

穷举法：

穷举法是最容易想到的算法。对于X的所有序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列。并且在检查中记录最长公共子序列。因此，共有2^m个子序列，从而穷举法需要时间指数。但时间复杂度和空间复杂度过高，不建议使用。

备忘录法：

【最长公共子序列】

package edu.xalead;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;

public class 最长公共子序列备忘录法 {
	public static int Ics(char[] x, char[] y, int i, int j,int[][] bak) {
		if(bak[i][j] !=-1) {
			return bak[i][j];
		}
		if (i  == 0 || j  == 0)
		    bak[i][j] = 0 ;
		else if (x[i] == y[j])
			bak[i][j] = Ics(x, y, i - 1, j - 1,bak) + 1;
		else
			bak[i][j] = max(Ics(x, y, i - 1, j,bak), Ics(x, y, i, j - 1,bak));
		return bak[i][j];
	}

	private static int max(int a, int b) {
		if (a > b)
			return a;
		else
			return b;

	}

	public static void main(String[] args) {
		String s1 = "ABCBDAB";
		
		char[] c1 = new char[s1.length() + 1];//带0号字符的字符数组
		char[] t1 = s1.toCharArray();
		c1[0] = (char)0;
		for(int i=0;i<t1.length;i++) {
			c1[i+1] = t1[i];
		}
		
		
		String s2 = "BDCABA";
		char[] c2 = new char[s2.length() + 1];//带0号字符的字符数组
		char[] t2 = s2.toCharArray();
		c2[0] = (char)0;
		for(int i=0;i<t2.length;i++) {
			c2[i+1] = t2[i];
		}
		
		int[][] bak = new int[c1.length][c2.length];
		for(int i=0;i<c1.length;i++) {
			for(int j=0;j<c2.length;j++) {
				bak[i][j] = -1;
			}
		}
		
		System.out.println(Ics(c1,c2,c1.length-1,c2.length-1,bak));
	}
}

自底向上法：

【最长公共子序列】

package edu.xalead;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;

public class 最长公共子序列自底向上法 {
	public static int Ics(char[] x, char[] y, int i, int j,int[][] bak) {
		for(int  ii=0;ii<=i;ii++) {
			for(int jj=0;jj<=j;jj++) {
				if (ii == 0 || jj == 0)
				    bak[ii][jj] = 0 ;
				else if (x[ii] == y[jj])
					bak[ii][jj] = bak[ii-1][jj-1] + 1;
				else //x[ii] != y[jj];
					bak[ii][jj] = max(bak[ii-1][jj],bak[ii][jj-1]);
			}
		}
		
		return bak[i][j];
	}

	private static int max(int a, int b) {
		if (a > b)
			return a;
		else
			return b;

	}

	public static void main(String[] args) {
		String s1 = "ABCBDAB";
		
		char[] c1 = new char[s1.length() + 1];//带0号字符的字符数组
		char[] t1 = s1.toCharArray();
		c1[0] = (char)0;
		for(int i=0;i<t1.length;i++) {
			c1[i+1] = t1[i];
		}
		
		
		String s2 = "BDCABA";
		char[] c2 = new char[s2.length() + 1];//带0号字符的字符数组
		char[] t2 = s2.toCharArray();
		c2[0] = (char)0;
		for(int i=0;i<t2.length;i++) {
			c2[i+1] = t2[i];
		}
		
		int[][] bak = new int[c1.length][c2.length];
//		for(int i=0;i<c1.length;i++) {
//			for(int j=0;j<c2.length;j++) {
//				bak[i][j] = -1;
//			}
		
		
		System.out.println(Ics(c1,c2,c1.length-1,c2.length-1,bak));
	}
}

【最长公共子序列】

相关推荐