最长公共子序列（LCS）
这两天编程涉及到求两个字符串的最长公共子序列问题，于是便重新复习之前一直没弄懂的最长公共子序列算法，也算是弄懂了一点。
算法分析：
采用动态规划方法来解决问题，将最长公共子序列问题转变为较小的问题。设两个字符串分别为 A=”a(0),a(1),…,a(m-1)”，B=”b(0),b(1),…,b(n-1)”，设Z=”z(0),z(1),…,z(k-2)”为它们的最长公共子序列。很容易看出：
（1）如果a(m-1)=b(m-1)，则z(k-1)=a(m-1)=b(m-1)，且”z(0),z(1),…,z(k-2)”是”a(0),a(1),…,a(m-2)”和”b(0),b(1),…,b(n-2)”的一个最长公共子序列；
（2）如果a(m-1)!=b(m-1)，则若z(k-1)!=a(m-1)，蕴含”z(0),z(1),…,z(k-1)”是”a(0),a(1),…,a(m-2)”和”b(0),b(1),…,b(n-1)”的一个最长公共子序列；
（3）如果a(m-1)!=b(m-1)，则若z(k-1)!=b(m-1)，蕴含”z(0),z(1),…,z(k-1)”是”a(0),a(1),…,a(m-1)”和”b(0),b(1),…,b(n-2)”的一个最长公共子序列。
使用一个(m+1)*(n+1)de二维数组c,c[i][j]存储序列”a(0),a(1),…,a(m-1)”和B=”b(0),b(1),…,b(n-1)”的最长公共子序列的长度，由递推关系可得递推关系式：
（1）c[i][j]=0，若i=0或j=0;
（2）c[i][j]=c[i-1][j-1]+1，若i,j>0且a[i-1]=b[j-1];
（3）c[i][j]=max(c[i][j-1],c[i-1][j])，若i,j>0且a[i-1]!=b[j-1]。
最终c[i][j]存储最长公共子序列的长度。
| 下标j
上标i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
| yj | B | D | C | A | B | A | ||
| 0 | xi | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 2 | B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| 3 | C | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| 4 | B | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
| 5 | D | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| 6 | A | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
| 7 | B | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
代码实现如下：
public static int compute(char[] str1, char[] str2){int substringLength1 = str1.length;int substringLength2 = str2.length;// 构造二维数组记录子问题A[i]和B[j]的LCS的长度int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];// 从后向前，动态规划计算所有子问题。也可从前到后。for (int i = substringLength1 - 1; i >= 0; i--){for (int j = substringLength2 - 1; j >= 0; j--){if (str1[i] == str2[j])opt[i][j] = opt[i + 1][j + 1] + 1;// 状态转移方程elseopt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);// 状态转移方程}}System.out.println("substring1:" + new String(str1));System.out.println("substring2:" + new String(str2));System.out.print("LCS:");int i = 0, j = 0;while (i < substringLength1 && j < substringLength2){if (str1[i] == str2[j]){System.out.print(str1[i]);i++;j++;}else if (opt[i + 1][j] >= opt[i][j + 1])i++;elsej++;}System.out.println();return opt[0][0];}public static int compute(String str1, String str2){return compute(str1.toCharArray(), str2.toCharArray());}
将该算法进行改进，实现求两个字符串的最长公共子序列，此时两个字符串的子序列不仅仅是一个字母，而有可能是一个英文字符串。如：[ai]man*jian*shen*和[ai]man*dian*shen*tai*yuan*jian*。首先将两个字符串分别通过正则式切割为多个字符串，并存入list集合，然后应用改进的LCS算法求这两个字符串的“最长公共子序列”。
| 下标j
上标i | 0 | 1 | 2 | 3 | 4 | |
| strj | ai | man | jian | shen | ||
| 0 | stri | 0 | 0 | 0 | 0 | 0 |
| 1 | ai | 0 | 1 | 1 | 1 | 1 |
| 2 | man | 0 | 1 | 2 | 2 | 2 |
| 3 | dian | 0 | 1 | 2 | 2 | 2 |
| 4 | shen | 0 | 1 | 2 | 2 | 3 |
| 5 | tai | 0 | 1 | 2 | 2 | 3 |
| 6 | yuan | 0 | 1 | 2 | 2 | 3 |
| 7 | jian | 0 | 1 | 2 | 3 | 3 |
java代码如下：
/**求两个字符串的最长公共子序列（拼音分隔后存入list，然后求其最长公共子序列。*/public static int LCS(String str1,String str2){String [] sub1 = str1.split("[*|?|\\[|\\]]");String [] sub2 = str2.split("[*|?|\\[|\\]]");List<String> strList1 = new ArrayList<>();List<String> strList2 = new ArrayList<>();for(String s:sub1){if(!s.equals("") && !s.equals("-")){strList1.add(s);}}for(String s:sub2){if(!s.equals("") && !s.equals("-")){strList2.add(s);}}int substringLength1 = strList1.size();int substringLength2 = strList2.size();// 构造二维数组记录子问题A[i]和B[j]的LCS的长度int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];// 从后向前，动态规划计算所有子问题。也可从前到后。for (int i = strList1.size() - 1; i >= 0; i--){for (int j = strList2.size() - 1; j >= 0; j--){if (strList1.get(i).equals(strList2.get(j)))opt[i][j] = opt[i + 1][j + 1] + 1;// 状态转移方程elseopt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);// 状态转移方程}}System.out.println("substring1:" + new String(str1));System.out.println("substring2:" + new String(str2));System.out.print("LCS:");int i = 0, j = 0;while (i < substringLength1 && j < substringLength2){if (strList1.get(i).equals(strList2.get(j))){System.out.print(strList1.get(i));i++;j++;}else if (opt[i + 1][j] >= opt[i][j + 1])i++;elsej++;}System.out.println();return opt[0][0];}public static void main(String[] args) {String str1 = "[ai]man*jian*shen*";String str2 = "[ai]man*dian*shen*tai*yuan*jian";System.out.println(LCS(str1,str2));} *求两个字符串的最长公共子序列（拼音分隔后存入list，然后求其最长公共子序列。*/public static int LCS(String str1,String str2){String [] sub1 = str1.split("[*|?|\\[|\\]]");String [] sub2 = str2.split("[*|?|\\[|\\]]");List<String> strList1 = new ArrayList<>();List<String> strList2 = new ArrayList<>();for(String s:sub1){if(!s.equals("") && !s.equals("-")){strList1.add(s);}}for(String s:sub2){if(!s.equals("") && !s.equals("-")){strList2.add(s);}}int substringLength1 = strList1.size();int substringLength2 = strList2.size();// 构造二维数组记录子问题A[i]和B[j]的LCS的长度int[][] opt = new int[substringLength1 + 1][substringLength2 + 1];// 从后向前，动态规划计算所有子问题。也可从前到后。for (int i = strList1.size() - 1; i >= 0; i--){for (int j = strList2.size() - 1; j >= 0; j--){if (strList1.get(i).equals(strList2.get(j)))opt[i][j] = opt[i + 1][j + 1] + 1;// 状态转移方程elseopt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);// 状态转移方程}}System.out.println("substring1:" + new String(str1));System.out.println("substring2:" + new String(str2));System.out.print("LCS:");int i = 0, j = 0;while (i < substringLength1 && j < substringLength2){if (strList1.get(i).equals(strList2.get(j))){System.out.print(strList1.get(i));i++;j++;}else if (opt[i + 1][j] >= opt[i][j + 1])i++;elsej++;}System.out.println();return opt[0][0];}public static void main(String[] args) {String str1 = "[ai]man*jian*shen*";String str2 = "[ai]man*dian*shen*tai*yuan*jian";System.out.println(LCS(str1,str2));}
运行结果如下：
今天特意记录下来，以便以后复习。如有错误之处，欢迎指正。
亦凉
朴灿烈づ我的快乐病毒、
分手后的思念是犯贱
你的名字
傷城~
还没有评论，来说两句吧...