問(wèn)題描述
LCS問(wèn)題可以分作最長(zhǎng)公共子序列問(wèn)題和最長(zhǎng)公共子集問(wèn)題参咙，其區(qū)別在于前者要求的是連續(xù)的屬于兩個(gè)字符串序列的子集，而后者則不要求連續(xù)硫眯。如：
字符串一：桃李漫山過(guò)眼空蕴侧。也宜惱損杜陵翁。若將玉骨冰姿比两入，李蔡為人在下中净宵。
字符串二：過(guò)眼滔滔云共霧，算人間知己吾和汝裹纳。人有病择葡，天知否？
一時(shí)書袋一時(shí)爽剃氧，一直吊一直爽敏储！
公共子集
公共子序列
問(wèn)題解析
公共子集
現(xiàn)有兩個(gè)字符串str_1,str_2，str_1.subString[0,m+1]和str.subString[0,n+1]代表這兩個(gè)字符串的前m項(xiàng)和前n項(xiàng)她我。LCS_1(String,String)方法返回兩個(gè)字符串的最長(zhǎng)公共子集虹曙。傳參中兩個(gè)字符串可以分立到兩個(gè)互補(bǔ)的場(chǎng)景中考慮即兩個(gè)字符串的尾項(xiàng)是否相等迫横。
尾項(xiàng)相等
由公共子集的特性可知番舆，相同的尾項(xiàng)一定會(huì)給最終的LCS結(jié)果作出+1的貢獻(xiàn)，所以在這種情況下數(shù)學(xué)表達(dá)式為：
LCS_1(str_1.subString(0,m+1),str.subString(0,n+1))= LCS_1(str_1.subString(0,m),str.subString(0,n))+1
尾項(xiàng)不相等
尾項(xiàng)不相等時(shí)我們分別考慮兩個(gè)字符串除去尾項(xiàng)的情況矾踱。所以表達(dá)式為：
LCS_1(str_1.subString(0,m+1),str.subString(0,n+1))= max(LCS_1(str_1.subString(0,m+1),str.subString(0,n))恨狈，LCS_1(str_1.subString(0,m),str.subString(0,n+1)))
最后加入初始條件和邊界條件即構(gòu)成了此題的動(dòng)態(tài)規(guī)劃算法。
公共子序列
本題需要構(gòu)建兩個(gè)字符串在每個(gè)位置上的重合矩陣呛讲。如"12345"和"34567"：
00100
00010
00001
00000
00000
此時(shí)矩陣只保存了位置重合與否信息禾怠，我們對(duì)其進(jìn)行優(yōu)化，當(dāng)str_2[m]與str_2[n]為相同字符時(shí)贝搁，arr[m][n]的值為arr[m-1][n-1]+1吗氏。此時(shí)矩陣變?yōu)?
00100
00020
00003
00000
00000
現(xiàn)在矩陣中已經(jīng)包含有公共子串的長(zhǎng)度信息，于是我們維護(hù)一個(gè)整型保存當(dāng)前循環(huán)中的LCS長(zhǎng)度并維護(hù)一個(gè)Stack<Integer>(為了兼容同時(shí)存在多個(gè)LCS解的情況)以獲得該子串尾項(xiàng)在矩陣中的坐標(biāo)雷逆。到了這一步我們犧牲了O(nm)的空間復(fù)雜度換得了O(nm)的時(shí)間復(fù)雜度弦讽。但是仍有方法進(jìn)一步減少內(nèi)存空間的損耗。上述前提中我們已經(jīng)通過(guò)開辟整型和棧在當(dāng)前循環(huán)中保存了最長(zhǎng)長(zhǎng)度以及結(jié)果坐標(biāo)，因此我們無(wú)需再維護(hù)一個(gè)完整而冗雜的矩陣往产，而只需要維護(hù)矩陣中當(dāng)前循環(huán)中使用的每一行(即單行)即可被碗。唯一需要注意的問(wèn)題是算法要求保存前一行中arr[m-1][n-1]的狀態(tài)，因此我們通過(guò)逆序刷新的方式仿村，如此一來(lái)在循環(huán)到arr[m]時(shí)锐朴，arr[m-1]保存的正是上一個(gè)循環(huán)中的字符重合狀態(tài)。
不嚴(yán)謹(jǐn)代碼
import java.util.Scanner;
import java.util.Stack;
/**
* 任意輸入兩個(gè)字符串蔼囊，求出這兩個(gè)字符串的公共子序列
* */
public class LCS1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String x = sc.next();
String y = sc.next();
getLCS(x,y);
sc.close();
}
public static void getLCS(String x, String y){
char[] s1 = x.toCharArray();
char[] s2 = y.toCharArray();
int her = x.length();
int ver = y.length();
int[][] array = new int[her][ver];
for(int m = 0; m < her; m++){//filling the LCS matrix using dynamic planning
for(int n = 0; n < ver; n++){
if(s1[m] == s2[n]){
if(m==0 || n==0) array[m][n] = 1;//default case
else array[m][n] = array[m-1][n-1] + 1;
}else{
if(m==0 || n==0) array[m][n] = 0;//default case
else array[m][n] = max(array[m -1][n], array[m][n -1]);
}
}
}
// for(int m = 0; m < her; m++){//output the auxiliary matrix
// for(int n = 0; n < ver; n++){
// System.out.print(array[m][n]);
// }
// System.out.println();
// }
Stack<Character> stack = new Stack<>();
int i = x.length() - 1;
int j = y.length() - 1;
while((i >= 0) && (j >= 0)){//push result into stack
if(s1[i] == s2[j]){
stack.push(s1[i]);
i--;
j--;
}else{
if(i==0) j--;
else if(j==0) i--;
else if(array[i][j-1] > array[i-1][j]){
j--;
}
else{
i--;
}
}
}
while(!stack.isEmpty()){
System.out.print(stack.pop());
}
}
public static int max(int a, int b){
return (a > b)? a : b;
}
}
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
public class LCS2 {
public static List<String> findLongestCommonSet(String str1,String str2){
char[] chArr1 = str1.toCharArray();
int len1 = chArr1.length;
char[] chArr2 = str2.toCharArray();
int len2 = chArr2.length;
Stack<Integer> indexes = new Stack<>();
List<String> res = new ArrayList<String>();
int maxLen = 0;
int[] lenArr = new int[len1>len2?len1:len2];
for(int i=0;i<len1;i++) {
for(int j=len2-1;j>=0;j--) {//fill and flush the single array by reversed order
if(chArr1[i]==chArr2[j]) {
if(i==0 || j==0) lenArr[j] = 1;//default case
else lenArr[j] = lenArr[j-1]+1;
}
else lenArr[j]=0;
/*record every largest length
* with corresponding indexes of last char
*/
if(lenArr[j]>maxLen) {
indexes.clear();
maxLen = lenArr[j];
indexes.push(j);
}
else if(lenArr[j]==maxLen) indexes.push(j);
}
}
while(!indexes.isEmpty()) {
int term = indexes.pop();
res.add(str2.substring(term-maxLen+1,term+1));
}
System.out.println("Longest Common Sequence："+maxLen);
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String x = sc.next();
String y = sc.next();
List<String> list = findLongestCommonSet(x, y);
for (int i = 0; i < list.size(); i++) {
System.out.println("第" + (i + 1) + "個(gè)公共子串:" + list.get(i));
}
sc.close();
}
}
