最長公共子字序列和最長公共子字元串

最長公共子串（Longest CommonSubstring）和最長公共子序列（LongestCommon Subsequence, LCS）的差別：子串（Substring）是串的一個連續的部分，子序列（Subsequence）則是從不改變序列的順序，而從序列中去掉任意的元素而獲得的新序列；更簡略地說，前者（子串）的字元的位置必須連續，後者（子序列LCS）則不必。比如字元串acdfg同akdfc的最長公共子串為df，而他們的最長公共子序列是adf。LCS可以使用動态規劃法解決。

一、最長公共子序列

   考慮最長公共子序列問題如何分解成子問題，設A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-1”，并Z=“z0，z1，…，zk-1”為它們的最長公共子序列。不難證明有以下性質：

（1） 如果am-1==bn-1，則zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一個最長公共子序列；

（2） 如果am-1!=bn-1，則若zk-1!=am-1時，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一個最長公共子序列；

（3） 如果am-1!=bn-1，則若zk-1!=bn-1時，蘊涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一個最長公共子序列。

解決方法：

引進一個二維數組c[][]，用c[i][j]記錄X[i]與Y[j] 的LCS 的長度，b[i][j]記錄c[i][j]是通過哪一個子問題的值求得的，以決定輸出最長公共字串時搜尋的方向。

      我們是自底向上進行遞推計算，那麼在計算c[i,j]之前，c[i-1][j-1]，c[i-1][j]與c[i][j-1]均已計算出來。此時我們根據X[i] == Y[j]還是X[i] != Y[j]，就可以計算出c[i][j]。

      問題的遞歸式寫成：

  回溯輸出最長公共子序列過程：

代碼如下：

public static int getCommonSubsequence(String A,String B){
	if(A==null||A.length()==0){
		return 0;
	}
	if(B==null||B.length()==0){
		return 0;
	}
		
	int lenA=A.length();
	int lenB=B.length();
		
	int[][] c=new int[lenA+1][lenB+1];//注意這個地方增加了一行和一列
	int maxLen=0;
		
	for(int i=0;i<lenA+1;i++){
		c[i][0]=0;  //第0列都初始化為0  
	}
	//j=0時c[i][j]=0
	for(int j=0;j<lenB+1;j++){
		c[0][j]=0;//第0行都初始化為0  
	}
	//
	for(int i=1;i<lenA+1;i++){
		for(int j=1;j<lenB+1;j++){
			//對應第一個性質 
			if(A.charAt(i-1)==B.charAt(j-1)){//由于c[][]的0行0列沒有使用，c[][]的第i行元素對應str1的第i-1個元素  
				c[i][j]=c[i-1][j-1]+1;
			}
			else{
				c[i][j]=Math.max(c[i-1][j], c[i][j-1]);
			}
		}
	}
	for(int i=1;i<lenA+1;i++){
		for(int j=1;j<lenB+1;j++){
			if(maxLen<c[i][j]){
				maxLen=c[i][j];
			}
		}
	}
	return maxLen;
		
}
           

二、最長公共子字元串

解法一、動态規劃的思想

動态轉移方程為：

（1） i=0時，如果xi == yj，c[i][j]=1;如果xi ! = yj,  那麼c[i][j] = 0

（2）j=0時，  如果xi== yj，c[i][j]=1;如果xi ! = yj,  那麼c[i][j] = 0

（3） i>=1&&j>=1時，如果xi == yj， 則 c[i][j] = c[i-1][j-1]+1； 如果xi ! = yj,  那麼c[i][j] = 0

比如字元串"acaccbabb"和字元串"acbac"可以得到這樣的C[i][j]，如下所示：

a c a c c b a b b
a 1 0 1 0 0 0 1 0 0 
c 0 2 0 2 1 0 0 0 0 
a 0 0 0 0 0 2 0 1 1 
c 1 0 1 0 0 0 3 0 0 
c 0 2 0 2 1 0 0 0 0 
           

代碼如下：

public  int getCommonSubString(String a,String b){
	if(a==null||a.length()==0||b==null||b.length()==0){
		return 0;
	}
		
	int lenA=a.length();//字元串a的長度
	int lenB=b.length();//字元串b的長度
		
	int[][] c=new int[lenA][lenB];
	int maxLen=1;
	//第（1）種情況
	for(int i=0;i<lenA;i++){
		if(a.charAt(i)==b.charAt(0)){
			c[i][0]=1;
		}
		else
			c[i][0]=0;
	}
		
	//第（2）種情況
	for(int j=0;j<lenB;j++){
		if(a.charAt(0)==b.charAt(j)){
			c[0][j]=1;
				
		}
		else
			c[0][j]=0;
	}
		
	//第（3）種情況
	for(int i=1;i<lenA;i++){
		for(int j=1;j<lenB;j++){
			if(a.charAt(i)==b.charAt(j)){
				c[i][j]=c[i-1][j-1]+1;
			}
			else
				c[i][j]=0;
		}
	}
	//找出從c[][]數組中的最大值，即為最長公共子字元串的長度
	for(int i=0;i<lenA;i++){
		for(int j=0;j<lenB;j++){
			if(c[i][j]>maxLen){
				maxLen=c[i][j];
			}
		}
	}
		
	return maxLen;
}
           

解法二（來源于：http://blog.csdn.net/hackbuteer1/article/details/6686931）

将字元串s1和s2分别寫在兩把直尺上面(我依然用s1，s2來表示這兩把直尺)，然後将s1固定，s2的頭部和s1的尾部對齊，然後逐漸移動直尺s2，比較重疊部分的字元串中的公共子串的長度，直到直尺s2移動到s1的頭部。在這個過程中求得的最大長度就是s1、s2最大子串的長度。

     下圖是求解過程的圖示（下圖有點錯誤，應該是将s2從右往左移動），藍色部分表示重疊的字元串，紅色的部分表示重疊部分相同的子串

      其中s1="shaohui"，s2="ahui"，最後求得的結果為3

我實作的代碼如下：

public static  int getCommonSubString(String a,String b){
	if(a==null||a.length()==0||b==null||b.length()==0){
		return 0;
	}
		
	int lenA=a.length();//字元串a的長度
	int lenB=b.length();//字元串b的長度
	int len=lenA+lenB;
	int max=0;
	for(int i=0;i<len;i++){
		int a_start=0;
		int b_start=0;
		if(i<lenA){
			a_start=lenA-i;
		}
		else{
			b_start=i-lenA;
		}
		int curMax=0;
		for(int j=0;(a_start+j<lenA)&&(b_start+j<lenB);j++){
			if(a.charAt(a_start+j)==b.charAt(b_start+j)){
				curMax++;
			}
			else{
				max=Math.max(curMax, max);
				curMax=0;
			}
				
		}
		max=Math.max(curMax, max);
			
	}
	return max;
}
           

參考：Java動态規劃 實作最長公共子序列以及最長公共子字元串