?題目標(biāo)題：

---

計(jì)算兩個字符串的最長公共子序列的長度，字符不區(qū)分大小寫。

輸入描述：輸入兩個字符串，分兩行輸入。

輸出描述：輸出一個整數(shù)。

示例：

輸入：

?測試數(shù)據(jù)1(注，字符串前有空格)：

12asdfawe2rasdaswer

輸出：6

測試數(shù)據(jù)2：

ABCADAB BACDBA

輸出：4

結(jié)果：

?LCS是Longest Common Subsequence的縮寫，即最長公共子序列。一個序列，如果是兩個或多個已知序列的子序列，且是所有子序列中最長的，則為最長公共子序列。

比如，對于char x[]="aabcd";有順序且相互相鄰的aabc是其子序列，有順序但是不相鄰的abc也是其公共子序列。即，只要得出序列中各個元素屬于所給出的數(shù)列，就是子序列。再加上char y[]="12abcabcd";對比出才可以得出最長公共子序列abcd。

---

最長公共子序列動態(tài)規(guī)劃解法：
dp[i][j] -- 表示子串A[0...i]（數(shù)組長度為n）和子串B[0...j]（數(shù)組長度為m）的最長公共子序列

當(dāng)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]);最優(yōu)解為dp[n-1][m-1];

---

JAVA代碼實(shí)現(xiàn)：

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];} }

?

總結(jié)

以上是生活随笔為你收集整理的最长公共子序列（JAVA实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。