这篇文章主要介绍“Java最长公共子序列是什么”，在日常操作中，相信很多人在Java最长公共子序列是什么问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java最长公共子序列是什么”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
public class LongestCommonSubsequence3 {
public static void main(String[] args) {
LongestCommonSubsequence3 lcs = new LongestCommonSubsequence3();
System.out.println(lcs.compute("ABCBDAB","BDCABA"));
}
public static int compute(char[] str1, char[] str2)
{
int substringLength2 = str1.length;
int substringLength3 = str2.length;
// 构造二维数组记录子问题A[i]和B[j]的LCS的长度,默认初始化为0
int[][] chess = new int[substringLength2 + 1][substringLength3 + 1];
// 从从前到后，动态规划计算所有子问题。也可从前向后
for (int i = 1; i <= substringLength2; i++)
{
for (int j = 1; j <= substringLength3; j++)
{
if (str1[i - 1] == str2[j - 1])
chess[i][j] = chess[i - 1][j - 1] + 1;// 状态转移方程
else
chess[i][j] = Math.max(chess[i - 1][j], chess[i][j - 1]);// 状态转移方程
}
}
System.out.println("substring1:" + new String(str1));
System.out.println("substring2:" + new String(str2));
System.out.print("LCS:");
int i = str1.length, j = str2.length;
String temp = "";
while (i != 0 && j != 0)
{
if (str1[i - 1] == str2[j - 1])
{
temp += str1[i - 1];
i--;
j--;
}
else{
if (chess[i][j - 1] > chess[i - 1][j])
j--;
else
i--;
}
}
for (int k = temp.length() - 1; k >= 0; k--) {
System.out.print(temp.toCharArray()[k]);
}
System.out.println();
return chess[str1.length][str2.length];
}
public int compute(String str1, String str2)
{
return compute(str1.toCharArray(), str2.toCharArray());
}
}
//================
public class LongestCommonSubsequence2 {
public static void main(String[] args) {
LongestCommonSubsequence2 lcs = new LongestCommonSubsequence2();
System.out.println(lcs.compute("ABCBDAB","BDCABA"));
}
public static int compute(char[] str1, char[] str2)
{
int substringLength2 = str1.length;
int substringLength3 = str2.length;
// 构造二维数组记录子问题A[i]和B[j]的LCS的长度
int[][] opt = new int[substringLength2 + 1][substringLength3 + 1];
// 从后向前，动态规划计算所有子问题。也可从前到后。
for (int i = substringLength2 - 1; i >= 0; i--)
{
for (int j = substringLength3 - 1; j >= 0; j--)
{
if (str1[i] == str2[j])
opt[i][j] = opt[i + 1][j + 1] + 1;// 状态转移方程
else
opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);// 状态转移方程
}
}
System.out.println("substring1:" + new String(str1));
System.out.println("substring2:" + new String(str2));
System.out.print("LCS:");
int i = 0, j = 0;
while (i < substringLength2 && j < substringLength3)
{
if (str1[i] == str2[j])
{
System.out.print(str1[i]);
i++;
j++;
}
else if (opt[i + 1][j] >= opt[i][j + 1])
i++;
else
j++;
}
System.out.println();
return opt[0][0];
}
public int compute(String str1, String str2)
{
return compute(str1.toCharArray(), str2.toCharArray());
}
}
//====================
package com.lifeibigdata.algorithms.string;
/**
* Created by lifei on 16/5/25.
*/
public class LongestCommonSubsequence {
public static void main(String[] args) {
char[] x = {' ','A','B','C','B','D','A','B'};
char[] y = {' ','B','D','C','A','B','A'};
LongestCommonSubsequence lcs = new LongestCommonSubsequence();
lcs.printLCS(lcs.lcsLength(x, y), x, x.length-1, y.length-1);
}
void printLCS(int[][] b,char[] x,int i,int j){
if(i == 0 || j == 0)
return;
if(b[i][j] == 1){
printLCS(b,x,i - 1,j - 1);
System.out.print(x[i] + "\t");
}else if(b[i][j] == 2)
printLCS(b,x,i - 1,j);
else
printLCS(b,x,i,j - 1);
}
int[][] lcsLength(char[] x,char[] y){
int m = x.length;
int n = y.length;
int i,j;
int[][] c = new int[m][n];
int[][] b = new int[m][n];
for(i = 1;i < m;i++)
c[i][0] = 0;
for(j = 0;j < n;j++)
c[0][j] = 0;
for(i = 1;i < m;i++)
for(j = 1;j < n;j++){
if(x[i] == y[j]){
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 1;
}
else if(c[i - 1][j] >= c[i][j - 1]){
c[i][j] = c[i - 1][j];
b[i][j] = 2;
}else{
c[i][j] = c[i][j - 1];
b[i][j] = 3;
}
}
return b;
}
}
/**
* 滚动数组只求大小,可以降低空间复杂度,时间复杂度不变
* 求全部的lcs，使用深搜或广搜
* 求有几个lcs，即只求lcs数目，计算有多少分支，即2的多少次方
*
*
*/
到此，关于“Java最长公共子序列是什么”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
