最长公共子序列的定义:
最长公共子序列问题是在一组序列(通常2个)中找到最长公共子序列(注意:不同于子串,LCS不需要是连续的子串)。该问题是典型的计算机科学问题,是文件差异比较程序的基础,在生物信息学中也有所应用。
最长公共子串的定义:
子串的字符应该连续的出现在原字符串中,这与子序列有所不同。
用动态规划来做,空间复杂度为o(n^2), 时间复杂度为o(n^2)
空间复杂度可优化到o(n)
最长公共子序列
状态方程为:12// ch1 = A.charAt(i), ch2 = B.charAt(j)dp[i][j] = ch1 == ch2 ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1])
比如:
^ | s | e | q | u | e | n | c | e | |
---|---|---|---|---|---|---|---|---|---|
^ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
s | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
c | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 |
i | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 |
e | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 3 |
n | 0 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 |
c | 0 | 1 | 2 | 2 | 2 | 2 | 3 | 4 | 4 |
e | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 4 | 5 |
|
|
最长公共子串
状态方程为:12// ch1 = A.charAt(i), ch2 = B.charAt(j)dp[i][j] = ch1 == ch2 ? dp[i - 1][j - 1] + 1 : 0
最后返回出现过的最长的数值
|
|