Saturday, December 12, 2015

Boyer-Moore Substring Match Algorithm

Boyer-Moore algorithm can give sublinear(best-case) as well as quadratic time performance(worst-case). Like KMP, it precomputes information necessary to search the subtring in the text.

Substring search with the Boyer-Moore mismatched character heuristic takes about ~(N/M) character compares to search for a pattern of length M in a text of length N. It can be ~MN in the worst case.

(Algorithms Part II -

Source :

import java.util.Arrays;

public class BoyerMoore {
    static String s, sub;
    static int[] pre;
    static int R = 257;
    public static int find(){
        pre = new int[R+1];
        Arrays.fill(pre, -1);
        int W = sub.length();
        int i, skip = 0;
            skip = 0;
            for(int j=W-1;j>=0;j--){ 
                    skip = Math.max(1, j-pre[s.charAt(i+j)]);
            if(skip==0)return i;
        return -1;
    public static void precompute(){
        for(int i=0;i<sub.length();++i){
            pre[sub.charAt(i)] = i;
    public static void main(String[] args){
        s = "thereisaneedleinthehaystack";
        sub = "needle";
        System.out.println("Substring found at index = "+find());
        sub = "nothing";
        System.out.println("Substring found at index = "+find());


Substring found at index = 8
Substring found at index = -1

No comments:

Post a Comment