Java最长公共子序列是什么

66次阅读
没有评论

共计 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;
 }

正文完
 
丸趣
版权声明:本站原创文章,由 丸趣 2023-08-16发表,共计3429字。
转载说明:除特殊说明外本站除技术相关以外文章皆由网络搜集发布,转载请注明出处。
评论(没有评论)