的Java：最長公共子

Question

我有以下代碼：

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<row;i++) 
     { 
     for(j=0;j<col;j++) 
     { 
      if(i==0||j==0) 
      { 
      c[i][j]=0; 
      } 
     } 
    } 
    for(i=1;i<=row;i++) 
    { 
     for(j=1;j<=col;j++) 
     { 
     if(str1.charAt(i-1)==str2.charAt(j-1)) 
     { 
      c[i][j]=c[i-1][j-1]+1; 
     } 
     else 
     { 
      c[i][j]=max(c[i][j-1],c[i-1][j]); 
     } 
     } 
    } 
    for(i=0;i<=row;i++) 
    { 
     for(j=0;j<=col;j++) 
     { 
     System.out.print(c[i][j]); 
     } 
     System.out.print("\n"); 
    } 
    for(i=row,j=col;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); 
    } 
}