Java: Longest common subsequence

Ho il seguente codice:

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

Deve restituire “out” ma una stringa vuota restituisce qual è il problema?

  • Il problema è che non hai eseguito un debugger.
  • Quando si trova una corrispondenza, non è necessario aggiungere che il carattere alla fine del ricorsiva risultato?



3 Replies
  1. 10

    Non sono sicuro, ma credo che le linee

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

    deve essere modificato

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

    Altrimenti non concatenazione di stringhe avviene e solo "" viene restituito.

    • grazie thank u molto
  2. 1
    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();
    }
  3. 0

    Forse questo sarà il lavoro:

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

Lascia un commento