首先說一下最長公共子序列和最長公共子串的差別。公共最長子序列是可以對你要比較的字元串進行一個或多個的字元删除後所留下的串，不要求一定連續。而最長公共子串要求結果的串一定是連續的。
例如：String s1=”ABCD”;
Stirng s2=”BCAD”;
是以最長公共子序列是BCD.而最長公共子串是BC.
下面介紹算法的具體實作。首先，我們建構一個二維數組dp[][]用來存放最長公共子串的值。仍然以上面的S1,S2為例。dp[][]數組的大小為：行數為S1的長度，列為S2的長度。是以我們就建構了一個4*4的數組。dp[i][j]的含義是s1[0…i]和s2[0….j]的最長公共子序列的長度。
B Ｃ Ａ D
A
B
C
D
首先，我們看豎着的這列的第一個字元A,也就是S1[0],用它和橫着的BCAD的第一個字元開始比較，若相等，就令dp[0][0]=1,并且剩下的dp[0][0…j]都為1。因為一個字元和BCAD進行比較，求公共最長子序列，那麼最大的值最多為1。并且，前面的若為1，後面的字元哪怕是不相等，但是至少也會有1(即前面相等的1);若不等，令dp[0][0]=0;接下來，繼續用A比較第二個字元即A和C,不等設dp[0][1]為0和前面的值比較所得的較大值,相等設為1.這樣我們就得到dp[][]的第0行為 0 0 1 1；同理我們用s2[0]和s1[0..i]比較，我們得到第0列為：
1
1
1
是以dp[][]的第一行第一列為 ：0 0 1 1
1
1
1
那麼我們繼續看dp[][]剩下的位置，其位置的值隻能來自下面的三種情況。①來自于dp[i-1][j] 。例如：s1=”A1BC2” s2=”AB34C” dp[3][4]即s1[0..3]和s2[0..4] 他們的最長公共子序列為ABC 是以dp[3][4]=3。dp[4][4]即求s1[0..4]和s2[0..4] 他們的最長公共子序列，也為ABC,是以dp[4][4]也為3.也就是證明了dp[4][4]可能來自于dp[3][4]。
②來自于dp[i][j-1]。例如S1=”A1B2C” s2=”AB3C4” dp[4][3]即S1[0..4]和S2[0..3] 他們的最長公共子序列為“ABC”是以dp[4][3]=3。dp[4][4]也等于3. 也就是證明了dp[4][4]可能來自于dp[4][3]。
③如果S1[i]==S2[j],還可能是dp[i-1][j-1]+1;例如：1=”ABCD” S2=”ABCD” dp[2][2]為3.dp[3][3]為4，即dp[2][2]+1;
綜上dp[i][j]取以上三種情況值為最大的那種。是以完整的dp數組如下：
B C A D
Ａ０0 1 1
Ｂ 1 1 1 1
Ｃ 1 2 2 2
Ｄ 1 2 2 3
dp[][]矩陣最右下角的值為最長公共子序列的長度。此題為3.求解dp[][]j矩陣代碼如下：
public static int[][] finddp(String s1, String s2) {
char[] a = s1.toCharArray();
char[] b = s2.toCharArray();
int[][] dp = new int[a.length][b.length];
dp[][] = a[] == b[] ? : ;
for (int i = ; i < a.length; i++) {
dp[i][] = Math.max(dp[i - ][], a[i] == b[] ? : );
}
for (int j = ; j < b.length; j++) {
dp[][j] = Math.max(dp[][j - ], b[j] == a[] ? : );
}
for (int i = ; i < a.length; i++) {
for (int j = ; j < b.length; j++) {
dp[i][j] = Math.max(dp[i - ][j], dp[i][j - ]);
if (a[i] == b[j]) {
dp[i][j] = Math.max(dp[i - ][j - ] + , dp[i][j]);
}
}
}
return dp;
}
既然dp[][]矩陣已經構造完成，那麼我們隻要通過這個矩陣的狀态就能得到最長公共子序列。步驟其實就是建構dp[][]過程的逆序。
①從dp[][]矩陣的右下角開始移動，可以有三種走法，向上，向左，向左上。用i表示行數，用j表示列，res表示結果。
②如果dp[i][j]大于dp[i-1][j]和dp[i][j-1],說明dp[i][j]是由dp[i-1][j-1]+1得來的，也就是說S1[i]==S2[j],該字元也是包含在最長公共子串的。是以把該字元加在res裡。
③如果dp[i][j]等于dp[i-1][j],說明計算dp[i][j]的時候不是由dp[i-1][j-1]+1得來的。是以隻需向上移動即可。
④如果dp[i][j]等于dp[i][j-1],說明計算dp[i][j]的時候不是由dp[i-1][j-1]+1得來的。是以隻需向左移動即可。
⑤如果dp[i][j]等于dp[i][j-1]和dp[i-1][j],那麼向上還是向左走都一樣的，随意選一條無所謂。
public static void main(String[] args) {
String s1 = "abcd";
String s2 = "acbd";
int i = s1.length() - ;
int j = s2.length() - ;
int[][] dp = finddp(s1, s2);
char[] res = new char[dp[s1.length() - ][s2.length() - ]];
int k = res.length - ;
while (k >= ) {
if (i > && dp[i - ][j] == dp[i][j]) {
i--;
} else if (j > && dp[i][j - ] == dp[i][j]) {
j--;
} else {
res[k--] = s1.charAt(i);
i--;
j--;
}
}
System.out.println(String.valueOf(res));
}
注：以上借鑒程雲老師的算法講解。