最长公共子串/子序列

最长公共子序列的定义
最长公共子序列问题是在一组序列(通常2个)中找到最长公共子序列(注意:不同于子串,LCS不需要是连续的子串)。该问题是典型的计算机科学问题,是文件差异比较程序的基础,在生物信息学中也有所应用。
最长公共子串的定义:
子串的字符应该连续的出现在原字符串中,这与子序列有所不同。
用动态规划来做,空间复杂度为o(n^2), 时间复杂度为o(n^2)
空间复杂度可优化到o(n)

最长公共子序列

状态方程为:

1
2
// 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
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
public class Solution {
/**
* @param A, B: Two strings.
* @return: The length of longest common subsequence of A and B.
*/
public int longestCommonSubsequence(String A, String B) {
// write your code here
if (A == null || A.length() == 0 || B == null || B.length() == 0) {
return 0;
}
int len1 = A.length();
int len2 = B.length();
int[] dp = new int[len2];
int thePrevDpj = 0;
int saveCurrDpj = 0;
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
saveCurrDpj = dp[j];
if (A.charAt(i) == B.charAt(j)) {
if (j == 0 || i == 0) {
dp[j] = 1;
} else {
dp[j] = thePrevDpj + 1;
}
} else {
if (i == 0 && j == 0) {
dp[j] = 0;
} else if (i == 0) {
dp[j] = dp[j - 1];
} else if (j == 0) {
dp[j] = dp[j];
} else {
dp[j] = Math.max(dp[j - 1], dp[j]);
}
}
thePrevDpj = saveCurrDpj;
}
}
return dp[len2 - 1];
}
}

最长公共子串

状态方程为:

1
2
// ch1 = A.charAt(i), ch2 = B.charAt(j)
dp[i][j] = ch1 == ch2 ? dp[i - 1][j - 1] + 1 : 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
public class Solution {
/**
* @param A, B: Two string.
* @return: the length of the longest common substring.
*/
public int longestCommonSubstring(String A, String B) {
// write your code here
if (A == null || A.length() == 0 || B == null || B.length() == 0) {
return 0;
}
int len1 = A.length();
int len2 = B.length();
int[] dp = new int[len2];
int prevDpj = 0;
int saveDpj = 0;
int max = 0;
for (int i = 0; i < len1; i++) {
for (int j = 0; j < len2; j++) {
saveDpj = dp[j];
if (A.charAt(i) == B.charAt(j)) {
if (i == 0 || j == 0) {
dp[j] = 1;
} else {
dp[j] = prevDpj + 1;
}
} else {
dp[j] = 0;
}
prevDpj = saveDpj;
max = Math.max(dp[j], max);
}
}
return max;
}
}