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

我会带着你远行 2024-04-17 16:27 37阅读 0赞

## 题目标题： ##

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

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

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

\* 示例：

\* 输入：

\* 12asdfa  
\* we2rasdaswer

\* 输出：6

LCS是Longest Common Subsequence的缩写，即最长公共子序列。一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为[最长公共子序列][Link 1]。

比如，对于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];
        }
    }

[Link 1]: https://baike.baidu.com/item/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97/8010952