C# Boyer-Moore String Search Example

In this article, I will show you the implementation of the Boyer-Moore algorithm. By the end of the post you will learn

• What is Boyer-Moore string search algorithm?
• How to implement Boyer-Moore string search algorithm in C#
• You can easily convert the algorithm to other language like Java,C++ or JavaScript

The Boyer-Moore string search algorithm is a dynamic programming algorithm that finds all occurrences of a given pattern in a text. Unlike the naive approach of checking each character in the text, it examines only those characters that are likely to be an occurrence of. The advantage of The Boyer-Moore string search algorithm is a fast and efficient way to find a substring in a text, such as a word in a sentence.

public class Search
    {
        private static int[] BuildBadCharTable(char[] needle)
        {
            int[] badShift = new int[256];
            for (int i = 0; i < 256; i++)
            {
                badShift[i] = needle.Length;
            }
            int last = needle.Length - 1;
            for (int i = 0; i < last; i++)
            {
                badShift[(int)needle[i]] = last - i;
            }
            return badShift;
        }

        public static int boyerMooreHorsepool(String pattern, String text)
        {
            char[] needle = pattern.ToCharArray();
            char[] haystack = text.ToCharArray();

            if (needle.Length > haystack.Length)
            {
                return -1;
            }
            int[] badShift = BuildBadCharTable(needle);
            int offset = 0;
            int scan = 0;
            int last = needle.Length - 1;
            int maxoffset = haystack.Length - needle.Length;
            while (offset <= maxoffset)
            {
                for (scan = last; (needle[scan] == haystack[scan + offset]); scan--)
                {
                    if (scan == 0)
                    { //Match found
                        return offset;
                    }
                }
                offset += badShift[(int)haystack[offset + last]];
            }
            return -1;
        }

    }