Noob
0%

最长公共子序列/子串(LCS)

发表于 更新于 分类于 ，

求最长公共子序列

使用DP算法，i, j分别表示,s1和s2的下标，转移方程为:

  • dp[i][j] = 0; if(i == 0 || j == 0)
  • dp[i][j] = dp[i - 1][j - 1] + 1; if(s1[i] == s2[j])
  • dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); if(s1[i] != s2[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
31
32
33
34
35
36
37
38
public String Lcsequence(String s1, String s2) {
    if(s1 == null || s2 ==null || s1.length() == 0 || s2.length() == 0)
        return "";
    int[][] dp = new int[s1.length() + 1][s2.length() + 1];
    int[][] flag = new int[s1.length() + 1][s2.length() + 1];
    for(int i = 0; i < s1.length(); ++i) {
        for(int j = 0; j < s2.length(); ++j) {
            if(s1.charAt(i) == s2.charAt(j)) {
                dp[i + 1][j + 1] = dp[i][j] + 1;
                flag[i + 1][j + 1] = 1;
            }
            else if(dp[i][j + 1] >= dp[i + 1][j]) {
                dp[i + 1][j + 1] = dp[i][j + 1];
                flag[i + 1][j + 1] = 2;
            } else {
                dp[i + 1][j + 1] = dp[i + 1][j];
                flag[i + 1][j + 1] = 3;
            }
        }
    }
    System.out.println(dp[s1.length()][s2.length()]);
    StringBuilder tmp = new StringBuilder();
    getLcs(s1, s2, s1.length(), s2.length(), flag, tmp);
    return tmp.toString();
}

public void getLcs(String s1, String s2, int len1, int len2, 
        int[][] flag, StringBuilder tmp) {
    if(len1 < 1 || len2 < 1) return;
    if(flag[len1][len2] == 1) {
        getLcs(s1,s2, len1 - 1, len2 - 1, flag, tmp);
        tmp.append(s1.charAt(len1 - 1));
    }
    else if(flag[len1][len2] == 2)
        getLcs(s1,s2, len1 - 1, len2, flag, tmp);
    else if(flag[len1][len2] == 3)
        getLcs(s1,s2, len1, len2 - 1, flag, tmp);
}

求最长公共子串

求最长公共子串的思路与求最长公共子序列基本一样，不同之处在于，只有i - 1， j - 1处字符相等i， j处的值才加1，如果不相等直接置0：

  • dp[i][j] = 0; if(i == 0 || j == 0)
    • dp[i][j] = dp[i - 1][j - 1]; if(s1[i] == s2[j])
    • dp[i][j] = 0; if(s1[i] != s2[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
public String lcstring(String s1, String s2) {
    if(s1 == null || s2 ==null) return "";
    int[][] dp = new int[s1.length() + 1][s2.length() + 1];
    int x = 0, y = 0;
    int max = 0;
    for(int i = 0; i < s1.length(); ++i) {
        for(int j = 0; j < s2.length(); ++j) {
            if(s1.charAt(i) == s2.charAt(j))
                dp[i + 1][j + 1] = dp[i][j] + 1;
            else
                dp[i + 1][j + 1] = 0;
            if(max < dp[i + 1][j + 1]) {
                x = i + 1;
                y = j + 1;
                max = dp[i + 1][j + 1];
            }
        }
    }
    char[] result = new char[max];
    while(max > 0) {
        result[--max] = s1.charAt(--x);
    }
    return new String(result);
}