Boyer Moore Algorithm in C++

This is a C++ Program to implement Boyer-Moore algorithm. The idea of bad character heuristic is simple. The character of the text which doesn’t match with the current character of pattern is called the Bad Character. Whenever a character doesn’t match, we slide the pattern in such a way that aligns the bad character with the last occurrence of it in pattern. We preprocess the pattern and store the last occurrence of every possible character in an array of size equal to alphabet size. If the character is not present at all, then it may result in a shift by m (length of pattern). Therefore, the bad character heuristic takes O(n/m) time in the best case.

Here is source code of the C++ Program to Implement Boyer-Moore Algorithm for String Matching. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

/* Program for Bad Character Heuristic of Boyer Moore String Matching Algorithm */

```
 
```
```
# include <limits.h>
```
```
# include <string.h>
```
```
# include <stdio.h>
```
```
 
```
```
# define NO_OF_CHARS 256
```
```
 
```

// A utility function to get maximum of two integers

```
int max(int a, int b)
```
```
{
```
```
    return (a > b) ? a : b;
```
```
}
```
```
 
```

// The preprocessing function for Boyer Moore's bad character heuristic

void badCharHeuristic(char *str, int size, int badchar[NO_OF_CHARS])

```
{
```
```
    int i;
```
```
 
```
```
    // Initialize all occurrences as -1
```
```
    for (i = 0; i < NO_OF_CHARS; i++)
```
```
        badchar[i] = -1;
```
```
 
```

    // Fill the actual value of last occurrence of a character

```
    for (i = 0; i < size; i++)
```
```
        badchar[(int) str[i]] = i;
```
```
}
```
```
 
```
```
void search(char *txt, char *pat)
```
```
{
```
```
    int m = strlen(pat);
```
```
    int n = strlen(txt);
```
```
 
```
```
    int badchar[NO_OF_CHARS];
```
```
 
```
```
    badCharHeuristic(pat, m, badchar);
```
```
 
```

    int s = 0; // s is shift of the pattern with respect to text

```
    while (s <= (n - m))
```
```
    {
```
```
        int j = m - 1;
```
```
 
```

        while (j >= 0 && pat[j] == txt[s + j])

```
            j--;
```
```
 
```
```
        if (j < 0)
```
```
        {
```

            printf("\n pattern occurs at shift = %d", s);

```
 
```

            s += (s + m < n) ? m - badchar[txt[s + m]] : 1;

```
 
```
```
        }
```
```
 
```
```
        else
```

            s += max(1, j - badchar[txt[s + j]]);

```
    }
```
```
}
```
```
 
```

/* Driver program to test above funtion */

```
int main()
```
```
{
```
```
    char txt[] = "ABAAABCD";
```
```
    char pat[] = "ABC";
```
```
    search(txt, pat);
```
```
    return 0;
```
```
}
```

Output:

$ g++ Boyer-Moore.cpp
$ a.out
 
pattern occurs at shift = 4
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

« Prev - C++ Program to Implement Aho-Corasick Algorithm for Pattern Searching

» Next - C++ Program to Solve any Linear Equation in One Variable

Related Posts:

Recommended Articles: