Saturday 31 March 2012

Find the Longest common sub sequence between two strings in java

My code:

static void LCS(String x, String y){
               int m = x.length();
               int n = y.length();
               int len[][] = new int[m+1][n+1]; // by default init. to zeros
               int b[][] = new int[m+1][n+1]; // by default init. to zeros
               for(int i=0;i<=m;i++){
                       for(int j=0;j<=n;j++){
                               if(i==0 || j==0){
                                       len[i][j] = 0;
                               }
                               else{
                                       if(x.charAt(i-1)==y.charAt(j-1)){
                                               len[i][j] = len[i-1][j-1] + 1;
                                               b[i][j] = -2;
                                       }
                                       else{
                                               if(len[i][j-1]>len[i-1][j]){
                                                       len[i][j] = len[i][j-1];
                                                       b[i][j] = -3;
                                               }else{
                                                       len[i][j] = len[i-1][j];
                                                       b[i][j] = -1;
                                               }

                                       }
                               }
                       }
               }
               System.out.println("length of LCS " + len[m][n]);
               int i=m,j=n;
               String res= "";
               while(true){

                       if(b[i][j] == -1){
                               i--;
                       }
                       if(b[i][j] == -2){
                               res = x.charAt(i-1)+ res;
                               i--;j--;
                       }
                       if(b[i][j] == -3){
                               j--;
                       }
                       if(res.length()==len[m][n])
                               break;
               }
               System.out.println("LCS " + res);
       }

No comments:

Post a Comment