Shulou(Shulou.com)05/31 Report--

This article mainly introduces "what is Java's longest common subsequence". In daily operation, I believe many people have doubts about what Java's longest common subsequence is. Xiaobian consulted all kinds of materials and sorted out simple and easy to use operation methods. I hope to help you answer the question of "what is Java's longest common subsequence"! Next, please follow the small series to learn together!

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; //Construct a 2D array to record the length of LCS for subproblems A[i] and B[j], initialized to 0 by default int[][] chess = new int[substringLength2 + 1][substringLength3 + 1]; //Dynamic programming computes all subproblems from front to back. Or from front to back. for (int i = 1; i = 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; //construct a two-dimensional array to record the length of the LCS of subproblems A[i] and B[j] int[][] opt = new int[substringLength2 + 1][substringLength3 + 1]; //From back to front, dynamic programming calculates all subproblems. Or from front to back. 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;//state transition equation else opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);//state transition equation } } 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; }}/** * Rolling array only size, can reduce space complexity, time complexity unchanged * Find all lcs, use deep search or wide search * Find how many lcs, that is, only the number of lcs, calculate how many branches, that is, how many powers of 2 * * */

At this point, the study of "what is the longest common subsequence of Java" is over, hoping to solve everyone's doubts. Theory and practice can better match to help everyone learn, go and try it! If you want to continue learning more relevant knowledge, please continue to pay attention to the website, Xiaobian will continue to strive to bring more practical articles for everyone!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.