1. 简介 LCS 通常是指Longest Common Subsequence, 但是也可代指Longest Common Substring。子串是一种特殊的子序列,子串和子序列的区别就是字串要求是组成子串的 各字符是连续的,而子序列仅仅要求各字符的下标是递增的即可。举个例子,如helloworld
, world
是子串(也是子序列), hw
不是子串是子序列。
LCS问题就是在若干(这里是两个)字符串中,找到最长的一个字符串p, 这个p是那些字符串的子串(子序列)。LCS问题的意义之一就是去衡量若干字符串的相似度,例如在生物信息学 中有DNA序列的问题,比如序列a = "ATGATAGATAGATAG"
, 序列b="TGGGCCGAGAAGCGAGA"
,需要一种去衡量a
、b
相似度的方法,那么最长公共子序列就可以作为一种衡量方法。 除此之外,在软件开发领域中的版本控制系统(典型的就是Git
),比较同一个文件不同时刻的差异的时候,就需要利用到这个方法。
例如下图就是Git
上面的两次不同时刻对同一个文件的快照的对比图,我们可以看到,系统把两次的差异标示出来了。而原来位置、内容相同的部分没有标示。这个就可以通过LCS
问题的解决,来找到最长的公共子序列部分,就是作为公共的、未发生改变部分;剩下的就是改变的部分,应该标示出来。
同理基于这个,我们还可以简单的比较两篇文章的相似度来检查雷同、抄袭的情况,这么看来,LCS问题的还是和我们日常比较相关的。
解决LCS问题依靠暴力(brute force)的求解时间复杂度是指数级别的,因此不太现实,由于问题的本身的最优解具有最优子结构 特征,因此原问题的求解可以化为多个子问题的求解;另外子问题的求解存在重叠的情况,这恰好是适合动态规划求解的问题的第二个特征:存在重叠的子问题求解过程 ,因此适合利用动态规划来求解,这个也是较常见的解决LCS问题的方法,时间复杂度为O(n*m)
,动态规划易于编写,但是时间复杂度较高;另外更高级的还存在一种线性复杂度的O(n+m)
的解法,就是Suffix Tree
,不过这种方法的缺点是程序难以编制。因此在日常的编码中,动态规划已经够用了。
2. 最长公共子串问题 设dp[i][j]表示s[0i]和t[0j]的最长公共子串的长度,对于两个字符串的最长公共子串问题的最优解,最优解存在如下结构:
1 2 3 4 dp[i][j] = 1 (i == 0 || j == 0) dp[i][j] = dp[i-1][j-1] + 1;(s[i] == t[j] && i > 0 && j > 0); dp[i][j] = 0;(s[i] != t[j])
上述等式建立了原问题和子问题的关系(此类证明可用反证法),剩下的就是编码了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 public static List<String> findLongestLCS (String s, String t) { char [] schs = s.toCharArray(); char [] tchs = t.toCharArray(); int m = s.length(), n = t.length(); int [][] dp = new int [m][n]; int maxSize = 0 ; List<Integer> indexs = new ArrayList <>(); for (int i = 0 ; i < m; i++) for (int j = 0 ; j < n; j++) { if (schs[i] == tchs[j]) { if (i == 0 || j == 0 ) dp[i][j] = 1 ; else dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; if (dp[i][j] > maxSize) { maxSize = dp[i][j]; indexs.clear(); indexs.add(i); } else if (dp[i][j] == maxSize) indexs.add(i); } else dp[i][j] = 0 ; } List<String> ret = new ArrayList <>(); for (Integer i : indexs) ret.add(s.substring(i + 1 - maxSize, i + 1 )); return ret; }
改进:上面的版本时间复杂度是O(n*m)
,空间复杂度也是O(n*m)
;但是观察dp二维数组发现,发现有优化的余地。由于在计算dp[i][j]的时候只使用到了dp[i-1][j-1],因此dp二维数组可以使用一个一位数组和两个临时变量即可完成,这样就把空间复杂度降低到O(min(n, m))
。
改进版本
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 public static List<String> findLongestLCS0 (String s, String t) { String tmp = s; if (s.length() > t.length()) { s = t; t = tmp; } char [] schs = s.toCharArray(); char [] tchs = t.toCharArray(); int m = s.length(), n = t.length(); int [] dp = new int [m]; int prev = 0 , cur = 0 ; int maxSize = 0 ; List<Integer> indexs = new ArrayList <>(); for (int i = 0 ; i < n; i++) for (int j = 0 ; j < m; j++) if (schs[j] == tchs[i]) { if (i == 0 || j == 0 ) dp[j] = 1 ; else { cur = dp[j]; dp[j] = prev + 1 ; prev = cur; } if (dp[j] > maxSize) { maxSize = dp[j]; indexs.clear(); indexs.add(j); } else if (dp[j] == maxSize) indexs.add(j); } else { cur = dp[j]; dp[j] = 0 ; prev = cur; } List<String> ret = new ArrayList <>(); for (Integer j : indexs) ret.add(s.substring(j + 1 - maxSize, j + 1 )); return ret; }
如果上面的dp数组很稀疏(0值很多),当字符串很大时,也还可以继续优化,采用hashmap
的方式存储非0值,这样在字符串大且dp数组稀疏的时候,可以进一步优化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 public static List<String> findLongestLCS1 (String s, String t) { String tmp = s; if (s.length() > t.length()) { s = t; t = tmp; } char [] schs = s.toCharArray(); char [] tchs = t.toCharArray(); int m = s.length(), n = t.length(); Map<Integer, Integer> dp = new HashMap <>(); int prev = 0 , cur = 0 ; int maxSize = 0 ; List<Integer> indexs = new ArrayList <>(); for (int i = 0 ; i < n; i++) for (int j = 0 ; j < m; j++) { Integer tmpj = dp.get(j); if (schs[j] == tchs[i]) { if (i == 0 || j == 0 ) dp.put(j, 1 ); else { cur = tmpj == null ? 0 : tmpj; dp.put(j, prev + 1 ); prev = cur; } tmpj = dp.get(j); if (tmpj > maxSize) { maxSize = tmpj; indexs.clear(); indexs.add(j); } else if (tmpj == maxSize) indexs.add(j); } else { cur = tmpj == null ? 0 : tmpj; dp.remove(j); prev = cur; } } System.out.println(indexs); List<String> ret = new ArrayList <>(); for (Integer j : indexs) ret.add(s.substring(j + 1 - maxSize, j + 1 )); return ret; }
3. 最长公共子序列问题 同样的最长公共子序列也可以利用刻画最优解的结构来利用DP求解。 对于字符串s和t,和上面一样dp[i][j]存储的值依然是s[0i]和t[0j]的最长公共子序列的长度。
最优解的结构
1 2 3 4 5 dp[i][j] = 1 (i == 0 || j == 0 && s[i] == t[j]) dp[i][j] = 0 (i == 0 || j == 0 && s[i] != t[j]) dp[i][j] = dp[i-1][j-1] + 1(i > 0 && j > 0 && s[i] == t[j]) dp[i][j] = max(dp[i-1][j], dp[i][j-1])(i > 0 && j > 0 && s[i] != t[j])
具体证明参见《算法讨导论》,也是利用反证法。
由于计算的时候只使用到了dp[i-1][j-1]、dp[i-1][j]和dp[i][j-1],则可以运用上上文中的思路,进行空间优化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 public static int longestLCS (String s, String t) { String tmp = s; if (s.length() > t.length()) { s = t; t = tmp; } char [] schs = s.toCharArray(); char [] tchs = t.toCharArray(); int m = s.length(), n = t.length(), prev = 0 , cur; int [] dp = new int [m]; for (int j = 0 ; j < n; j++) for (int i = 0 ; i < m; i++) { if (schs[i] == tchs[j]) { if (i == 0 || j == 0 ) dp[i] = 1 ; else { cur = dp[i]; dp[i] = prev + 1 ; prev = cur; } } else { cur = dp[i]; int aa = i == 0 ? 0 : dp[i-1 ], bb = j == 0 ? 0 : dp[i]; dp[i] = Math.max(aa, bb); prev = cur; } } return dp[m-1 ]; }
但是由于有些时候,我们需要知道这些最长公共子序列,因此我们还需要在求解的过程保存额外的信息(上文中保存的是下标值)。为了得到最长公共子序列,我们可以 沿着求解反方向去得到最长公共子序列。具体的做法就是,给定一个dp[i][j]我们可以判断出,它是由dp[i][j-1]还是dp[i-1][j]还是dp[i-1][j-1]得来的,知道了这个以后我们就知道了求解方向了,这样可以逆着回退到起点dp[0][0]。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 public static String longestLCSWithReconstructionLCS (String a, String b) { char [] achs = a.toCharArray(); char [] bchs = b.toCharArray(); int m = a.length(), n = b.length(); int [][] dp = new int [m][n]; StringBuilder sb = new StringBuilder (); for (int i = 0 ; i < m; i++) for (int j = 0 ; j < n; j++) { if (achs[i] == bchs[j]) { if (i == 0 || j == 0 ) dp[i][j] = 1 ; else dp[i][j] = dp[i - 1 ][j - 1 ] + 1 ; } else { int aa = i == 0 ? 0 : dp[i - 1 ][j], bb = j == 0 ? 0 : dp[i][j - 1 ]; dp[i][j] = Math.max(aa, bb); } } int i = m - 1 , j = n - 1 ; while (i >= 0 && j >= 0 ) { if (achs[i] == bchs[j]) { sb.append(achs[i]); i--;j--; } else { if (dp[i - 1 ][j] >= dp[i][j - 1 ]) i--; else j--; } } return sb.reverse().toString(); }
我们可以在O(n)
的时间重构得到最长公共子序列,由于我们需要在最后逆行构造最长公共子序列,因此是不能将二维数组dp优化成一位数组dp,因为优化以后我们是没法 在O(1)
的时间判断出由dp[i][j-1]还是dp[i-1][j]还是dp[i-1][j-1]得来的,重构最长公共子序列也就无从谈起了。
4. References [1] Longest_common_subsequence_problem
[2] Suffix Tree
[3] Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Clifford Stein.算法导论[M].北京:机械工业出版社,2015:222-226