LCS(substring) | LCS(subsequence) | LIS

发表于 | 分类于

LongestCommonSubstring 最长公共子串

动态规划解法：

dp[i][j]表示以si和tj结尾的公共子串的最大长度；
则转移方程为：
dp[i][j] = si == tj ? 1 : 0 , i==0||j==0
dp[i][j] = s1[i] == s2[j] ? dp[i-1][j-1]+1 : 0 ,other

CODE

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
/**
 * 最长公共子串
 * dp[i][j]表示以以i、j结尾的以s1[i]、s2[j]为结尾的相同子串的最大长度
 * dp[i][j] = s1[i] == s2[j] ? 1 : 0 ,i==0||j==0
 * dp[i][j] = s1[i] == s2[j] ? dp[i-1][j-1]+1 : 0
 */
    public static int longestCommonSubstring (String s1, String s2) {
        int[][] dp = new int[s1.length()][s2.length()];
        int max=0;
        int x=0,y=0;
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if (i == 0 || j == 0)
                    dp[i][j] = s1.charAt(i) == s2.charAt(j) ? 1 : 0;
                else
                    dp[i][j] = s1.charAt(i) == s2.charAt(j) ? dp[i - 1][j - 1] + 1 : 0;
                max = Math.max(max,dp[i][j]);
                if(max==dp[i][j]){
                    x=i;
                    y=j;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=x,j=y;i>=0&&j>=0&&dp[i][j]>=1;i--,j--)
            sb.append(s1.charAt(i));
        System.out.println(sb.reverse().toString());
        return max;
    }
    public static void main (String []args) {
        System.out.println(LCSubstring.longestCommonSubstring("acbcbce","abcbced"));
    }

NOTE
輸出最大子串：记录最大子串值和位置，沿对角线遍历（–1；–j），因为子串是连续的正确路径只会是对角线

LongesetCommonSubsequence 最长公共子序列

动态规划解法：

dp[i][j]表示s0…si与t0…tj最长公共子序列
转移方程：
dp[i][j] = s[i]== t[j] ? 1 : 0, i==0 and j==0;
dp[i][j] = s[i]== t[j] ? 1 : dp[i == 0 ? 0 : i - 1][j == 0 ? 0 : j - 1],i==0 or j==0 and i!=j;
dp[i][j] = dp[i-1][j-1] + 1, s[i] == t[j];
dp[i][j] = max(dp[i-1][j], dp[i][j-1]), s[i] != t[j];

CODE:

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
public static int LongestCommonSubsequence (String s1, String s2) {
       int[][] dp = new int[s1.length()][s2.length()];
       int max = 0;
       for (int i = 0; i < s1.length(); i++) {
           for (int j = 0; j < s2.length(); j++) {
               if (i == 0 && j == 0)
                   dp[i][j] = s1.charAt(i) == s2.charAt(j) ? 1 : 0;
               else if (i == 0 || j == 0) {
                   if (s1.charAt(i) == s2.charAt(j))
                       dp[i][j] = 1;
                   else
                       dp[i][j] = dp[i == 0 ? 0 : i - 1][j == 0 ? 0 : j - 1];
               } else {
                   if (s1.charAt(i) == s2.charAt(j))
                       dp[i][j] = dp[i - 1][j - 1] + 1;
                   else
                       dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
               }
               max = Math.max(max, dp[i][j]);
               System.out.print(dp[i][j]);
           }
           System.out.println();
       }
       return max;
   }

   public static void showSubsequence (int[][] dp, String s, String t) {
       int i = s.length() - 1, j = t.length() - 1;
       StringBuilder sb = new StringBuilder();
       while (i >= 0 && j >= 0) {
           if (s.charAt(i) == s.charAt(j)) {
               sb.append(s.charAt(i));
               ++i;
               ++j;
           } else {
           }
       }

   }

NOTE:关于输出，从dp表最后一位开始遍历，若相对的字符相等则添加，遍历–i与–j，若不等，比较–i，j与i，–j大小，遍历大者，
若相等（搞清楚后补充）。。。

LIS 最长非递减序列

动态规划解法：

dp[i]表示里nums[i]为结尾的lis
转移方程：
dp[i] = max(dp[i],d[j]+1),s[j]<=s[i]

CODE:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int LIS(int[] nums) {
        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            dp[i] = 1;
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] <= nums[i])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }

贪心+二分：

贪心：使得加入最后一位的值尽可能的小，这样序列才更容易增加
二分：搜索当前添加元素在已添加数组的下边界（加入的位置，数组都是排好序的）
将元素加入res数组，如果带加入的数字大于res数组的最后一位，则直接添加，否则二分查找要替换的位置,最后res数组大小即为结果（注意res数组内容并不是要求数列）

CODE:

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
/**
     * 贪心+二分 nlogn
     */
    public static int LIS (int[] nums) {
        int[] res = new int[nums.length];
        int size = 0;
        res[size++] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= res[size - 1]) {
                res[size++] = nums[i];
            } else {
                res[lower_bound(0, size - 1, res, nums[i])] = nums[i];
            }
        }
        return res.length;
    }

    /**
     * 二分查下界
     */
    public static int lower_bound (int left, int right, int[] nums, int target) {
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] >= target)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }
Thanks!