Skip to content
Boyer Moore string search implementation in C
C Makefile
Branch: master
Clone or download
likejazz Merge pull request #2 from siten/master
255 will Stack overflow
Latest commit d81fd74 Jun 24, 2015
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.gitignore
LICENSE remove extra whitespaces. Jul 3, 2014
Makefile refactored Jun 30, 2014
README.md remove extra whitespaces. Jul 3, 2014
boyer-moore.c Update boyer-moore.c Jun 21, 2015
sample-output.png renamed Jul 2, 2014

README.md

boyer-moore-string-search

Boyer-Moore string search algorithm implementation in C.

The algorithm performs its matching backwards, from right to left and proceeds by iteratively matching, shifting the pattern, matching, shifting, etc. The shift amount is calculated by applying these two rules:

  1. the bad character rule
  2. good suffix rule

An actual shifting offset is the maximum one of them.

  • delta1 - the "Bad Character" table

This table contains an entry for every character in the alphabet. The entry for char specifies how far the pattern should be right shifted when chars found in the string and it does not match the current pattern character.

  • delta2 - the "Good Suffix" table

This table contains an entry for each character in the pattern. The entry for pattern[j] specifies how far the current string position should shift to the right when pattern[j-1] does not match the string but the suffix at pattern[j .. patlen-1] does match.

Usage

To compile and execute the tests:

$ make
$ ./bm

To remove the compiled file:

$ make clean

Sample Output

Sample Output

You can’t perform that action at this time.