最长公共子串/子序列

发表于 | 分类于 ， |

最长公共子序列的定义：
最长公共子序列问题是在一组序列（通常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;
    }
}