Boyer Moore Algorithm in C

This is a C Program to implement Boyer-Moore algorithm. The Boyer-Moore algorithm is considered as the most efficient string-matching algorithm in usual applications. A simplified version of it or the entire algorithm is often implemented in text editors for the search and substitute commands.

The algorithm scans the characters of the pattern from right to left beginning with the rightmost one. In case of a mismatch (or a complete match of the whole pattern) it uses two precomputed functions to shift the window to the right. These two shift functions are called the good-suffix shift (also called matching shift and the bad-character shift (also called the occurrence shift).

Assume that a mismatch occurs between the character x[i]=a of the pattern and the character y[i+j]=b of the text during an attempt at position j.
Then, x[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u and x[i] != y[i+j]. The good-suffix shift consists in aligning the segment y[i+j+1 .. j+m-1]=x[i+1 .. m-1] with its rightmost occurrence in x that is preceded by a character different from x[i]

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.

```
# 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]]);

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

Output:

$ gcc Boyer-Moore.c
$ ./a.out
 
pattern occurs at shift = 4

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 Affine Cipher

» Next - C Program to Implement the Vigenere Cipher

Related Posts:

Recommended Articles: