LCS问题

发表于 | 分类于 | 阅读次数

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[0~i]和t[0~j]的最长公共子串的长度，对于两个字符串的最长公共子串问题的最优解，最优解存在如下结构：

1
2
3
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

// 内存改进版本, 只存储one row,新增两个临时变量空间复杂度O(min(m, n))
	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];
  //prev存储dp[i-1][j-1]，cur存储dp[i][j]
		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

// 内存改进版1 用hashtable存储每一行dp的非0值
	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 {
					//非0值不存储， 优化稀疏情况。
					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[0~i]和t[0~j]的最长公共子序列的长度。

最优解的结构

1
2
3
4
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

//只需要求解长度，可以进行空间优化
	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 ---> dp[i-1][j-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

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