17. BOYER MOORE PATTERN MATCHING

Code:

import java.util.*;

class BoyerMoore

{

     private String t,p;

     private int m, n;

     private int last[ ];

     private int count;

     public BoyerMoore(String t, String p)

    {

       this.t=t;

       this.p=p;

       n=t.length( );

       m=p.length( );

       last=new int[128];

    }

   public static int min(int a, int b)

  {

      if (a<b)

               return a;

      else  return b;

  }

   public int getNoOfComparisons( )

  {

     return count;

   }

    public void buildLast( )

  {

     for (int i=0; i<m; i++)

        last[(int)p.charAt(i)]=i;

  }

      public  int BoyerMooreMatch( )

     {

       int i, j;

      i=j=m-1;

      while(i<=n-1)

      {

        count++;

        if (p.charAt(j)==t.charAt(i))

            if (j==0)

                  return i;

            else

            {

               i--; j--;

            }

         else

         {

             i=i+m-min(j, 1+last[t.charAt(i)]);

             j=m-1;

         }

    }

    return -1;

 }

}

class BoyerMooreExp

{

      public static void main(String args[])

     {

         Scanner src = new Scanner(System.in);

         String text,pattern;

         System.out.println("Enter Text");

         text=src.nextLine();

         System.out.println("Enter Pattern");

         pattern=src.nextLine();

         BoyerMoore obj=new BoyerMoore(text,pattern);

         obj.buildLast( );

         int z=obj.BoyerMooreMatch( );

        if(z!=-1)

                System.out.println(pattern+" is present in "+text+" from index "+z+" to "+ (z+pattern.length()-1));

         else

                System.out.println(pattern +" is not present in "+text);

         System.out.println(" No of comparsions = "+ obj.getNoOfComparisons( ));

      }

}  

Need the code??

Download Link= https://www.dropbox.com/s/15xdxyu09dbhl7q/BoyerMooreExp.txt