Java Program to Search Pattern using Horspool Algorithm

Horspool Algorithm is used to search the pattern in the given string using a shift table. Its another variation of the Boyer-Moore Algorithm where it uses two shift tables - bad shift table and good suffix table but in Horspool Algorithm we are using just one shift table to search the pattern in the given string.

What is Shift Table in Horspool Algorithm ?

A shift table is the table that contains two things : -

1. Either length of the Pattern to be searched 
2. Or distance of first occurrence of each character from the right most side of the pattern.

To know more about the Horspool Algorithm 

import java.util.*;
public class Horspool  {
  
   public static int SIZE=500;    
   public static int table[]=new int[SIZE];
  
public void shifttable(String pattern) {
 
 int i,j,m;
 char p[] = pattern.toCharArray();
 m=pattern.length();
 
 for (i=0;i<SIZE;i++)
    table[i]=m;
 for (j=0;j<m;j++)
    table[p[j]]=m-1-j;
}
public int horspool(String source,String pattern)
  {
      int i,k,pos,m;
      char s[] = source.toCharArray();
      char p[] = pattern.toCharArray();
      m=pattern.length();
     
      for(i=m-1;i<source.length();)
        {
           k=0;
            while((k<m) && (p[m-1-k] == s[i-k]))
              k++;
           if(k==m) 
     {   pos=i-m+2;
               return pos;
     } 
           else
               i+=table[s[i]];
        }
        return -1;
  } 
     public static void main(String []args){
        int pos; 
  String source=args[0];
        String pattern = args[1];
  
        Horspool  h = new Horspool ();
        
        h.shifttable(pattern);
        pos = h.horspool(source,pattern);
  
        if(pos == -1)
            System.out.println("PATTERN NOT FOUND");
        else
            System.out.println("PATTERN FOUND FROM POSITION: \t"+pos+"\n");
     }
}

Please Click and Drag from the beginning to End of the above Source code for Selection and Copying.

  To compile and run :

javac Horspool.java
java Horspool Testingstring ting

Output :   PATTERN FOUND FROM POSITION:    4

Please Note :

Testingstring is the source string and ting is the Pattern to be Searched both are given while running the Java Program and are accepted using args[0]=Source String and args[1]=Pattern to be Search in the program. You can change this if you want in the program .Thank you.