最长公共子序列（JAVA实现）

 题目标题：

计算两个字符串的最长公共子序列的长度，字符不区分大小写。

输入描述：输入两个字符串，分两行输入。

输出描述：输出一个整数。

示例：

输入：

 测试数据1(注，字符串前有空格)：

  

   

    

     

    
    

     

       12asdfa
     
    
   

    

     

    
    

     

       we2rasdaswer
     
    
  
 

输出：6

测试数据2：

  

   

    

     

    
    

     

      ABCADAB
     
    
   

    

     

    
    

     

      BACDBA
     
    
  
 

输出：4

结果：

 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代码实现：

  

   

    

     

    
    

     

      import java.util.Scanner;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      public class Main {
     
    
   

    

     

    
    

     
    public static void main(String[] args) {
     
    
   

    

     

    
    

     
        Scanner scanner = new Scanner(System.in);
     
    
   

    

     

    
    

     
        while (scanner.hasNextLine()) {
     
    
   

    

     

    
    

     
            String str1 = scanner.nextLine().toLowerCase();
     
    
   

    

     

    
    

     
            String str2 = scanner.nextLine().toLowerCase();
     
    
   

    

     

    
    

     

                  System.out.println(findLCS(str1, str1.length(), str2, str2.length()));
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    public static int findLCS(String A, int n, String B, int m) {
     
    
   

    

     

    
    

     
        int[][] dp = new int[n + 1][m + 1];
     
    
   

    

     

    
    

     
        for (int i = 0; i <= n; i++) {
     
    
   

    

     

    
    

     
            for (int j = 0; j <= m; j++) {
     
    
   

    

     

    
    

     

                      dp[i][j] = 0;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        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;
     
    
   

    

     

    
    

     

                      } else {
     
    
   

    

     

    
    

     

                          dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
     
    
   

    

     

    
    

     

                      }
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        return dp[n][m];
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

文章来源: laoshifu.blog.csdn.net，作者：红目香薰，版权归原作者所有，如需转载，请联系作者。

原文链接：laoshifu.blog.csdn.net/article/details/117386998