Algorithm

最长公共子序列

最长公共子序列（LongestCommonSubsequence）

一个数列S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。
最长公共子序列问题可以由动态规划求解

动态规划

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化（en:memoization）存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。————维基百科

动态规划求解LCS

1.最优子结构性质

设输入序列是X [0 .. m-1] 和 Y [0 .. n-1]，长度分别为 m 和 n。和设序列 L(X [0 .. m-1]，Y[0 .. n-1]) 是这两个序列的 LCS 的长度，以下为 L(X [0 .. M-1]，Y [0 .. N-1]) 的递归定义：

1）如果两个序列的最后一个元素匹配（即X [M-1] == Y [N-1]）

　　 则：L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）

2）如果两个序列的最后字符不匹配（即X [M-1] != Y [N-1]）

　　 则：L(X [0 .. M-1]，Y [0 .. N-1]) = MAX(L(X [0 .. M-2]，Y [0 .. N-1])，L(X [0 .. M-1]，Y [0 .. N-2]))

2.重叠子问题

很明显，LCS 很多子问题也都共享子子问题，因此可以对其进行递归求解。具体的算法时间度为 O(m*n)，可以优化至 O(m+n)。

code

代码如下：

未优化

1
2
3
4
5
6
7
8
9
10
11
12
int Longest_Common_Subsequence(char *sa, int n1, char *sb, int n2)
{
	if (n1 > 0 && n2 > 0)
	{
		if (sa[n1 - 1] == sb[n2 - 1]) 
			return 1 + Longest_Common_Subsequence(sa, n1 - 1, sb, n2 - 1);
		else 
			return max(Longest_Common_Subsequence(sa, n1 , sb, n2 - 1),
			Longest_Common_Subsequence(sa, n1 - 1, sb, n2 ));
	}
	return 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
int lcs(char *sa, int n1, char *sb, int n2)
{
	int **ls = new int*[n1];
	for (int i = 0; i < n1; ++i)
	{
		ls[i] = new int[n2];
	}
	for (int i = 0; i < n1; ++i)
	{
		for (int j = 0; j < n2; ++j)
		{
			if (i == 0 || j == 0) ls[i][j] = 0;
			else if (sa[i - 1] == sb[j - 1]) ls[i][j] = ls[i - 1][j - 1] + 1;
			else ls[i][j] = max(ls[i - 1][j], ls[i][j - 1]);
		}
	}
	int tmp = ls[n1 - 1][n2 - 1];
	for (int k = 0; k < n1; ++k)
	{
		delete []ls[k];
	}
	delete []ls;
	return tmp;

}