Java：最常见的子序列

我有以下代码：

public class LCS1 { public static String lcs(String a, String b) { String x; String y; int alen = a.length(); int blen = b.length(); if (alen == 0 || blen == 0) { return ""; } else if (a.charAt(alen - 1) == b.charAt(blen - 1)) { return lcs(a.substring(0, alen - 1), b.substring(0, blen - 1)); } else { x = lcs(a, b.substring(0, blen - 1)); y = lcs(a.substring(0, alen - 1), b); } return (x.length() > y.length()) ? x : y; } public static void main(String[] args) { String a = "computer"; String b = "houseboat"; System.out.println(lcs(a, b)); } } 

它应该返回“ out ”但空字符串返回什么是问题？

Answer 1

我不确定，但我认为，线条

 else if (a.charAt(alen-1)==b.charAt(blen-1)){ return lcs(a.substring(0,alen-1),b.substring(0,blen-1)); } 

应该改为

 else if (a.charAt(alen-1)==b.charAt(blen-1)){ return lcs(a.substring(0,alen-1),b.substring(0,blen-1)) + a.charAt(alen-1); } 

否则，不会发生字符串串联，只返回"" 。

Answer 2

 public static String longestSubstring(String str1, String str2) { StringBuilder sb = new StringBuilder(); if (str1 == null || str1.isEmpty() || str2 == null || str2.isEmpty()) return ""; // ignore case str1 = str1.toLowerCase(); str2 = str2.toLowerCase(); // java initializes them already with 0 int[][] num = new int[str1.length()][str2.length()]; int maxlen = 0; int lastSubsBegin = 0; for (int i = 0; i < str1.length(); i++) { for (int j = 0; j < str2.length(); j++) { if (str1.charAt(i) == str2.charAt(j)) { if ((i == 0) || (j == 0)) num[i][j] = 1; else num[i][j] = 1 + num[i - 1][j - 1]; if (num[i][j] > maxlen) { maxlen = num[i][j]; // generate substring from str1 => i int thisSubsBegin = i - num[i][j] + 1; if (lastSubsBegin == thisSubsBegin) { // if the current LCS is the same as the last time // this block ran sb.append(str1.charAt(i)); } else { // this block resets the string builder if a // different LCS is found lastSubsBegin = thisSubsBegin; sb = new StringBuilder(); sb.append(str1.substring(lastSubsBegin, i + 1)); } } } } } return sb.toString(); } 

Answer 3

也许这会奏效：

 import java.util.*; class Main{ static int max(int num1,int num2) { if(num1> num2) return num1; else return num2; } public static void main(String args[]){ Scanner sc=newScanner(System.in); int n,i,j,count=0; String str1,str2; System.out.println("Enter String 1"); str1=sc.nextLine(); System.out.println("Enter String 2"); str2=sc.nextLine(); int row=str1.length(); int col=str2.length(); char LCS[]=new char[row+1]; int c[][]=new int[row+1][col+1]; for(i=0;i=0&&j>=1;) { if(c[i][j]!=c[i][j-1]) { LCS[count]=str1.charAt(i-1); j--; i--; count++; } else if(c[i][j]==c[i][j-1]) { j--; } } System.out.print("Longest Common Subsequence :- "); for(i=count-1;i>=0;i--) { System.out.print(LCS[i]); } System.out.print(“\n”+“Length OF Subsequence=”+count ); } }