LCS：又稱最長公共子序列。其中子序列(subsequence)的概念不同于串的子串。它是一個不一定連續(xù)但按順序取自字符串X中的字符序列。例如：串"AAAG"就是串“CGATAATTGAGA”的一個子序列。

字符串的相似性問題可以通過求解兩個串間的最長公共子序列(LCS)來得到。當然如果使用窮舉算法列出串的所有子序列，一共有2^n種，而每個子序列是否是另外一個串的子序列又需要O(m)的時間復雜度，因此這個窮舉的方法時間復雜度是O(m*(2^n))指數(shù)級別，效率相當?shù)目膳?。我們采用動態(tài)規(guī)劃算法來解決這個問題。

動態(tài)規(guī)劃算法解決最長公共子序列

假如我們有兩個字符串：X=[0,1,2....n] Y=[0,1,2...m]。我們定義L(i, j)為X[0...i]與Y[0...j]之間的最長公共子序列的長度。通過動態(tài)規(guī)劃思想(復雜問題的最優(yōu)解是子問題的最優(yōu)解和子問題的重疊性質(zhì)決定的)。我們考慮這樣兩種情況：

(1) 當X[i]=Y[j]時， L(i, j)=L(i-1, j-1)+1。證明很簡單。

(2) 當X[i]!=Y[j]時，說明此事X[0...i]和Y[0...j]的最長公共子序列中絕對不可能同時含有X[i]和Y[j]。那么公共子序列可能以X[i]結(jié)尾，可能以Y[j]結(jié)尾，可以末尾都不含有X[i]或Y[j]。因此

L(i, j)= MAX{L(i-1 , j), L(i, j-1)}

LCS動態(tài)規(guī)劃Java源代碼

package net.hr.algorithm.string;

/**
 * 最長公共子串LCS
 * @author heartraid
 */
public class LCS {

	/**字符串X的字符數(shù)組*/
	private char[] charArrayX=null;
	/**字符串Y的字符數(shù)組*/
	private char[] charArrayY=null;

	public LCS(String sa,String sb){
		charArrayX=new char[sa.length()+1];
		System.arraycopy(sa.toCharArray(),0,charArrayX,1,sa.length());
		charArrayY=new char[sb.length()+1];
		System.arraycopy(sb.toCharArray(),0,charArrayY,1,sb.length());
	}
	
	/**
	 * 得到最長公共子序列的長度
	 */
	public void getLCS(){
		
		int[][] length=new int[charArrayX.length+1][charArrayY.length+1];
		
		for(int m=1;m<charArrayX.length;m++)
			for(int n=1;n<charArrayY.length;n++){
				if(charArrayX[m]==charArrayY[n]){
					length[m][n]=length[m-1][n-1]+1;
				}
				else
					length[m][n]=max(length[m-1][n],length[m][n-1]);
					
			}
		//打印最長公共子序列
		String lcstr="";
		int x=charArrayX.length-1;
		int y=charArrayY.length-1;
		while(x>=1&&y>=1){
			if(charArrayX[x]==charArrayY[y]){
				lcstr=charArrayX[x]+lcstr;
				x--;
				y--;
			}else{
				if(length[x-1][y]<=length[x][y-1])
					y--;
				else
					x--;	
			}
		}
		System.out.println("最長公共子序列為："+lcstr+" [length="+lcstr.length()+"]");
	}
	/**
	 * 取最大值
	 */
	private int max(int m,int n){
		return m>n?m:n;
	}	
	
	/**
	 * 測試
	 */
	public static void main(String[] args) {
		LCS lcs=new LCS("GTTCCTAATA","CGATAATTGAGA");
		lcs.getLCS();
	}

}

這里解釋一下上面的代碼，其中getLength()的作用是遞歸獲取最長公共子串的長度，并得到遞歸過程中每個子串之間最長公共子串長度的狀態(tài)表lcs[][]，這張表運行的結(jié)果如下：

C G A T A A T T G A G A

0 0 0 0 0 0 0 0 0 0 0 0 0
G 0 0 1 1 1 1 1 1 1 1 1 1 1
T 0 0 1 1 2 2 2 2 2 2 2 2 2
T 0 0 1 1 2 2 2 3 3 3 3 3 3
C 0 1 1 1 2 2 2 3 3 3 3 3 3
C 0 1 1 1 2 2 2 3 3 3 3 3 3
T 0 1 1 1 2 2 2 3 4 4 4 4 4
A 0 1 1 2 2 3 3 3 4 4 5 5 5
A 0 1 1 2 2 3 4 4 4 4 5 5 6
T 0 1 1 2 3 3 4 5 5 5 5 5 6
A 0 1 1 2 3 4 4 5 5 5 6 6 6

紅色數(shù)字的位置就揭示了最長公共子序列： CTATTA。也就是說分析這張表就可以得到最長公共子序列字符串。

為什么呢？因為通過表的回溯過程，從后向前重構(gòu)了一個最長公共子序列。對于任何位置lcs[i][j]，確定是否X[i]=Y[j]。如果是，那么X[i]必是最長公共子序列的一個字符。如果否，那么移動到lcs[i,j-1]和lcs[i-1, j]之間的較大者。

動態(tài)規(guī)劃方法LCS效率：

動態(tài)規(guī)劃方法構(gòu)造最長公共子序列需要O(m*n)的代價，另外，如果想要得到最長公共子序列，又需要O(m+n)的時間來讀取csl[][]數(shù)組。盡管如此，其時間復雜度仍然比蠻力窮舉的指數(shù)級別要強的多。

問題拓展：設A,B,C是三個長為n的字符串，它們?nèi)∽酝怀?shù)大小的字母表。設計一個找出三個串的最長公共子串的O(n^3)的時間算法。(來自《Algorithm Design》(中文版：算法分析與設計) - Chapter9 - 文本處理 - 創(chuàng)新題C-9.18）

分析：可以通過《LCS最長公共子序列》的動態(tài)規(guī)劃算法，設計Java源代碼如下：

Java代碼

1. public class TriLCS{
3. char[] charA=null;
4. char[] charB=null;
5. char[] charC=null;
8. public TriLCS(String sa,String sb,String sc){
9. charA=new char[sa.length()+1];
10. System.arraycopy(sa.toCharArray(),0,charA,1,sa.length());
11. charB=new char[sb.length()+1];
12. System.arraycopy(sb.toCharArray(),0,charB,1,sb.length());
13. charC=new char[sc.length()+1];
14. System.arraycopy(sc.toCharArray(),0,charC,1,sc.length());
15. }
17. public void getTriLCS(){
19. int[][][] length=new int[charA.length][charB.length][charC.length];
21. for(int a=1;a<charA.length;a++)
22. for(int b=1;b<charB.length;b++)
23. for(int c=1;c<charC.length;c++){
25. if(charA[a]==charB[b]&&charA[a]==charC[c]){
26. length[a][b][c]=length[a-1][b-1][c-1]+1;
27. }
28. else if(charA[a]==charB[b]&&charA[a]!=charC[c]){
29. length[a][b][c]=max(length[a-1][b-1][c],length[a][b][c-1]);
30. }
31. else if(charA[a]==charC[c]&&charA[a]!=charB[b]){
32. length[a][b][c]=max(length[a-1][b][c-1],length[a][b-1][c]);
33. }
34. else if(charB[b]==charC[c]&&charA[a]!=charB[b]){
35. length[a][b][c]=max(length[a][b-1][c-1],length[a-1][b][c]);
36. }
37. else{
38. length[a][b][c]=max(length[a-1][b][c],length[a][b-1][c],length[a][b][c-1],length[a-1][b-1][c],length[a-1][b][c-1],length[a][b-1][c-1]);
39. }
40. }
44. //打印最長公共子序列
45. String lcstr="";
46. int a=charA.length-1;
47. int b=charB.length-1;
48. int c=charC.length-1;
49. while(a>=1&&b>=1&&c>=1){
50. if(charA[a]==charB[b]&&charA[a]==charC[c]){
51. lcstr=charA[a]+lcstr;
52. a--;
53. b--;
54. c--;
55. }
56. else if(charA[a]==charB[b]&&charA[a]!=charC[c]){
57. if(length[a-1][b-1][c]<=length[a][b][c-1])
58. c--;
59. else{
60. a--;
61. b--;
62. }
63. }
64. else if(charA[a]==charC[c]&&charA[a]!=charB[b]){
65. if(length[a-1][b][c-1]<=length[a][b-1][c])
66. b--;
67. else{
68. a--;
69. c--;
70. }
71. }
72. else if(charB[b]==charC[c]&&charA[a]!=charB[b]){
73. if(length[a][b-1][c-1]<=length[a-1][b][c])
74. a--;
75. else{
76. b--;
77. c--;
78. }
79. }
80. else{
81. int maxize=max(length[a-1][b][c],length[a][b-1][c],length[a][b][c-1],length[a-1][b-1][c],length[a-1][b][c-1],length[a][b-1][c-1]);
82. if(maxize==length[a-1][b][c])
83. a--;
84. if(maxize==length[a][b-1][c])
85. b--;
86. if(maxize==length[a][b][c-1])
87. c--;
88. if(maxize==length[a-1][b-1][c]){
89. a--;
90. b--;
91. }
92. if(maxize==length[a-1][b][c-1]){
93. a--;
94. c--;
95. }
96. if(maxize==length[a][b-1][c-1]){
97. b--;
98. c--;
99. }
100. }
101. }
103. System.out.println("最長子串為："+lcstr+"(length="+length[charA.length-1][charB.length-1][charC.length-1]+")");
104. }
106. /**
107. * 取最大值
108. */
109. private int max(int m,int n){
110. return m>n?m:n;
111. }
112. /**
113. * 取最大值
114. */
115. private int max(int x,int y,int z,int k,int m,int n){
116. int maxizen=0;
117. if(maxizen<x) maxizen=x;
118. if(maxizen<y) maxizen=y;
119. if(maxizen<z) maxizen=z;
120. if(maxizen<k) maxizen=k;
121. if(maxizen<m) maxizen=m;
122. if(maxizen<n) maxizen=n;
123. return maxizen;
124. }
126. public static void main(String[] args){
127. TriLCS tri=new TriLCS("aadsbbbcs","adsabcs","adbsbsdcs");
128. tri.getTriLCS();
129. }
130. }