Java最长公共子序列是什么

共计 3429 个字符，预计需要花费 9 分钟才能阅读完成。

这篇文章主要介绍“Java 最长公共子序列是什么”，在日常操作中，相信很多人在 Java 最长公共子序列是什么问题上存在疑惑，丸趣 TV 小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java 最长公共子序列是什么”的疑惑有所帮助！接下来，请跟着丸趣 TV 小编一起来学习吧！

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 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());

 }


 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;

 }