教育改变生活

标题: Java-最长公共子序列 [打印本页]

作者: 一秉 时间: 2020-5-15 19:06
标题: Java-最长公共子序列
      LCS是Longest Common Subsequence的缩写，即最长公共子序列。一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。
   比如，对于char x[]="aabcd";有顺序且相互相邻的aabc是其子序列，有顺序但是不相邻的abc也是其公共子序列。即，只要得出序列中各个元素属于所给出的数列，就是子序列。再加上char y[]="12abcabcd";对比出才可以得出最长公共子序列abcd。
      最长公共子序列动态规划解法：
      dp[i][j] -- 表示子串A[0...i]（数组长度为n）和子串B[0...j]（数组长度为m）的最长公共子序列
      当A[i] == B[j]时，dp[i][j] = dp[i-1][j-1] + 1;
      否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
      最优解为dp[n-1][m-1];
      JAVA代码实现：
public static int findLCS(String A, int n, String B, int m) {
      int[][] dp = new int[n + 1][m + 1];
      for (int i = 1; i <= n; i++) {
         for (int j = 1; j <= m; j++) {
            if (A.charAt(i - 1) == B.charAt(j - 1)) {
                  dp[i][j] = dp[i - 1][j - 1] + 1;//当A[i] == B[j]时，dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                  dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);//dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
         }
      }
      return dp[n][m];
}

欢迎光临教育改变生活 (http://bbs.goldoar.com/)