java实现最长公共子序列算法
时间: 2023-10-12 16:19:38 浏览: 65
最长公共子序列(Longest Common Subsequence, LCS)是指给定两个序列X和Y,找出它们的最长公共子序列。
以下是Java实现最长公共子序列算法的代码:
```java
public static int lcs(String X, String Y) {
int m = X.length();
int n = Y.length();
int[][] L = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
L[i][j] = 0;
} else if (X.charAt(i - 1) == Y.charAt(j - 1)) {
L[i][j] = L[i - 1][j - 1] + 1;
} else {
L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
}
}
}
return L[m][n];
}
```
代码中的L数组是用来记录最长公共子序列的长度的,其中L[i][j]表示X的前i个字符和Y的前j个字符的最长公共子序列的长度。算法的时间复杂度为O(mn)。
相关问题
用Java实现最长公共子序列
最长公共子序列问题是算法中一个经典的问题,通常可以使用动态规划算法来解决。下面是使用Java实现最长公共子序列的代码:
```java
public class LongestCommonSubsequence {
public static void main(String[] args) {
String str1 = "ABCDGHLQR";
String str2 = "AEDPHR";
int m = str1.length();
int n = str2.length();
System.out.println("Length of Longest Common Subsequence is " + lcs(str1, str2, m, n));
}
public static int lcs(String str1, String str2, int m, int n) {
int[][] lcsArray = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
lcsArray[i][j] = 0;
} else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
lcsArray[i][j] = 1 + lcsArray[i - 1][j - 1];
} else {
lcsArray[i][j] = Math.max(lcsArray[i - 1][j], lcsArray[i][j - 1]);
}
}
}
return lcsArray[m][n];
}
}
```
此代码中,我们首先定义了两个字符串变量 str1 和 str2,以及它们的长度 m 和 n。然后我们创建了一个二维数组lcsArray,用于存储计算过程中的中间值。
接下来,我们使用两层循环遍历str1和str2,并在每个位置上计算最长公共子序列的长度。如果str1和str2在当前位置上的字符相同,我们将lcsArray[i][j]设为1加上左上角位置的值;否则,我们将lcsArray[i][j]设置为上方或左方的值中的最大值。
最后,我们返回lcsArray[m][n],即最长公共子序列的长度。
用java实现最长公共子序列问题
最长公共子序列问题是指,给定两个字符串S1和S2,求它们的最长公共子序列LCS。
Java实现最长公共子序列问题可以使用动态规划算法,具体实现步骤如下:
1. 定义一个二维数组dp,其中dp[i][j]表示S1的前i个字符和S2的前j个字符的最长公共子序列的长度。
2. 初始化dp数组的第一行和第一列,即dp[0][j]和dp[i][0]都为0。
3. 对于任意的i>0和j>0,若S1的第i个字符等于S2的第j个字符,则dp[i][j] = dp[i-1][j-1] + 1;否则dp[i][j] = max(dp[i][j-1], dp[i-1][j])。
4. 最终,dp[S1.length()][S2.length()]的值即为S1和S2的最长公共子序列的长度。
下面是Java代码实现:
```
public static String LCS(String S1, String S2) {
int m = S1.length();
int n = S2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = 0;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (S1.charAt(i-1) == S2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}
}
}
int len = dp[m][n];
char[] lcs = new char[len];
int i = m, j = n;
while (i > 0 && j > 0) {
if (S1.charAt(i-1) == S2.charAt(j-1)) {
lcs[--len] = S1.charAt(i-1);
i--;
j--;
} else if (dp[i][j-1] > dp[i-1][j]) {
j--;
} else {
i--;
}
}
return new String(lcs);
}
```
调用LCS方法即可返回S1和S2的最长公共子序列。