PHP-Fusion Powered Website - Articles: C++ Program to Implement Boyer-Moore Algorithm for Pattern Searching

Users Online

· Guests Online: 52

· Members Online: 0

· Total Members: 188
· Newest Member: meenachowdary055

Forum Threads

Newest Threads

No Threads created

Hottest Threads

No Threads created

Latest Articles

· Do while loop
· The for loop in C
· C while loop
· Pointers in C
· Functions in C

Oh no! Where's the JavaScript?
Your Web browser does not have JavaScript enabled or does not support JavaScript. Please enable JavaScript on your Web browser to properly view this Web site,
or upgrade to a Web browser that does support JavaScript; Firefox, Safari, Opera, Chrome or a version of Internet Explorer newer then version 6.

Articles Hierarchy

Articles Home » C++ » C++ Program to Implement Boyer-Moore Algorithm for Pattern Searching

C++ Program to Implement Boyer-Moore Algorithm for Pattern Searching

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

Users Online

Forum Threads

Latest Articles

Articles Hierarchy

C++ Program to Implement Boyer-Moore Algorithm for Pattern Searching

C++ Program to Implement Boyer-Moore Algorithm for Pattern Searching

Comments

Post Comment

Ratings