Boyer Moore Algorithm in Java

In this tutorial, you will learn what is Boyer Moore Algorithm, what is it used for, and how to implement it in Java Programming Language.

What is the Boyer Moore Algorithm

It is an efficient string searching algorithm used to look for specific patterns in a string or a text file. The name Boyer Moore algorithm was named after the two who developed it i.e. Robert Boyer and J Strother Moore who established it in 1977. This algorithm uses the approach of gathering information during preprocessing to skip some sections of the text to reduce the constant factor. As the pattern length increases, this runs faster. This is said to be the benchmark for all algorithms.

Java Program: Boyer Moore Algorithm

Let us see the program for the algorithm

package javaapplication18;
public class JavaApplication18 {
    static int NO_OF_CHARS = 256; 
       static int max (int a, int b) { return (a > b)? a: b; } 
       static void badCharHeuristic( char []str, int size,int badchar[]) 
     { 
      int i; 
        for (i = 0; i < NO_OF_CHARS; i++) 
           badchar[i] = -1; 
        for (i = 0; i < size; i++) 
           badchar[(int) str[i]] = i; 
     } 
  
     static void search( char txt[],  char pat[]) 
     { 
      int m = pat.length; 
      int n = txt.length; 
  
      int badchar[] = new int[NO_OF_CHARS]; 
        badCharHeuristic(pat, m, badchar); 
  
      int s = 0;  
      while(s <= (n - m)) 
      { 
          int j = m-1; 
  
                   while(j >= 0 && pat[j] == txt[s+j]) 
              j--; 
  
          if (j < 0) 
          { 
              System.out.println("Patterns occur at shift = " + s); 
                s += (s+m < n)? m-badchar[txt[s+m]] : 1; 
            } 
  
          else
                          s += max(1, j - badchar[txt[s+j]]); 
      } 
     } 
  
       public static void main(String []args) { 
          
         char txt[] = "123651266512".toCharArray(); 
         char pat[] = "12".toCharArray(); 
         search(txt, pat); 
    } 
    
}

Output:

Patterns occur at shift = 0
Patterns occur at shift = 5
Patterns occur at shift = 10

Also read: What is CountDownLatch in Java

Leave a Reply

Your email address will not be published. Required fields are marked *