Array

Boyer Moore string search algorithm

Pinterest LinkedIn Tumblr

Boyer Moore string search algorithm is an efficient string searching algorithm that is the standard benchmark for practical string search literature. Write a program to implement Boyer Moore string search algorithm

Algorithm Explanation

Pass text and string arguments to the utility function.
Utility function implements the Algorithm and it scans the characters from right to left from the text.
If the text contains any mismatch from the string, it uses two precomputed functions to shift the window to the right. These two shift functions called the matching shift and the occurrence shift.
Return the string position.

Source Code

package com.dsacode.DataStructre.array;
 
public class StrMatchBoyerMoore {
    public int indexOf(char[] text, char[] pattern) {
        if (pattern.length == 0)
            return 0;
         
        int charTable[] = makeCharTable(pattern);
        int offsetTable[] = makeOffsetTable(pattern);
        for (int i = pattern.length - 1, j; i < text.length;)
        {
            for (j = pattern.length - 1; pattern[j] == text[i]; --i, --j)
                     if (j == 0)
                    return i;
              i += Math.max(offsetTable[pattern.length - 1 - j], charTable[text[i]]);
        }
        return -1;
      }
     
     
      private int[] makeCharTable(char[] pattern){
        final int ALPHABET_SIZE = 256;
        int[] table = new int[ALPHABET_SIZE];
        for (int i = 0; i < table.length; ++i)
               table[i] = pattern.length;
        for (int i = 0; i < pattern.length - 1; ++i)
               table[pattern[i]] = pattern.length - 1 - i;
        return table;
      }
       
       
      private static int[] makeOffsetTable(char[] pattern) {
        int[] table = new int[pattern.length];
        int lastPrefixPosition = pattern.length;
        for (int i = pattern.length - 1; i >= 0; --i) {
            if (isPrefix(pattern, i + 1))
                   lastPrefixPosition = i + 1;
              table[pattern.length - 1 - i] = lastPrefixPosition - i + pattern.length - 1;
        }
        for (int i = 0; i < pattern.length - 1; ++i) {
              int slen = suffixLength(pattern, i);
              table[slen] = pattern.length - 1 - i + slen;
        }
        return table;
    }
       
     
    private static boolean isPrefix(char[] pattern, int p)   {
        for (int i = p, j = 0; i < pattern.length; ++i, ++j)
            if (pattern[i] != pattern[j])
                  return false;
        return true;
    }
     
     
    private static int suffixLength(char[] pattern, int p) {
        int len = 0;
        for (int i = p, j = pattern.length - 1; i >= 0 && pattern[i] == pattern[j]; --i, --j)
               len += 1;
        return len;
    }
     
     
    public static void main(String[] args)  {   
 
        System.out.println("String pattern match using Boyer Moore Algorithm");
        StrMatchBoyerMoore bm = new StrMatchBoyerMoore();
        String t="hfgbcabdabcabd",p="ab";
        char[] text = t.toCharArray();
        char[] pattern = p.toCharArray();
         
        System.out.println("String Text:" + t +" Pattern:"+p);
         
        int pos = bm.indexOf(text, pattern);
        if (pos == -1)
            System.out.println("\nNo Match\n");
        else
            System.out.println("Pattern found at position : "+ pos);
         
      
    }
 
}

Output

String pattern match using Boyer Moore Algorithm
String Text:hfgbcabdabcabd Pattern:ab
Pattern found at position: 5

Write A Comment