Java: Longest common subsequence

Question

I have following code:

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

  }
}

It should return "out" but an empty string returns what is problem?

Answer 1

I'm not sure, but I think, the lines

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

should be changed to

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

Otherwise no concatenation of strings takes place and only "" is returned.

Answer 2

When you find a match, don't you need to append that character to the end of the recursive result?