Longest Common Subsequence

 public class LCSequence {  
      public String lcs(String a, String b) {  
           int[][] lengths = new int[a.length()+1][b.length()+1];  
           // row 0 and column 0 are initialized to 0 already  
           for (int i = 0; i < a.length(); i++)  
                for (int j = 0; j < b.length(); j++)  
                     if (a.charAt(i) == b.charAt(j))  
                          lengths[i+1][j+1] = lengths[i][j] + 1;  
                     else  
                          lengths[i+1][j+1] =  
                          Math.max(lengths[i+1][j], lengths[i][j+1]);  
           // read the substring out from the matrix  
           StringBuffer sb = new StringBuffer();  
           for (int x = a.length(), y = b.length();  
                     x != 0 && y != 0; ) {  
                if (lengths[x][y] == lengths[x-1][y])  
                     x--;  
                else if (lengths[x][y] == lengths[x][y-1])  
                     y--;  
                else {  
                     if(a.charAt(x-1) == b.charAt(y-1)){  
                          sb.append(a.charAt(x-1));  
                          x--;  
                          y--;  
                     }  
                }  
           }  
           System.out.println("The DP table is: ");   
           for (int i=0; i<lengths.length; i++) {   
                for (int j=0; j<lengths[i].length; j++) {   
                     System.out.print(" " + lengths[i][j]);   
                }   
                System.out.println("");   
           }   
           return sb.reverse().toString();  
      }  
      public static void main(String args[]){   
           LCSequence m = new LCSequence();   
           System.out.println("The LCS is "+m.lcs("12","1122"));   
      }   
 }