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