Boyer-Moore is an algorithm that improves the performance of pattern searching into a text by considering some observations. As in the naïve searching algorithm, the Boyer-Moore algorithm successively aligns pattern P with string T and then checks whether P matches the opposing characters of T. Further, after the check is complete, P is shifted right relative to T just as in the naive searching algorithm. The Boyer-Moore algorithm uses two different heuristics for determining the maximum possible shift distance in case of a mismatch: the “bad character” and the “good suffix” heuristics. Both heuristics can lead to a shift distance of m. For the bad character heuristics this is the case, if the first comparison causes a mismatch and the corresponding text symbol does not occur in the pattern at all. For the good suffix heuristics this is the case, if only the first comparison was a match, but that symbol does not occur elsewhere in the pattern.

The pre-processing for the good suffix heuristics is rather difficult to understand and to implement. Therefore, sometimes versions of the Boyer-Moore algorithm are found in which the good suffix heuristics is left away. The argument is that the bad character heuristics would be sufficient and the good suffix heuristics would not save many comparisons. However, this is not true for small alphabets. Together, these ideas lead to a method that typically examines fewer than m + n characters (an expected sub linear-time method), and that (with a certain extension) runs in linear worst case time.

Main features

  • Performs the comparisons from right to left;
  • Preprocessing phase in O(m+ ) time and space complexity;
  • Searching phase in O(mn) time complexity;
  • 3n text character comparisons in the worst case when searching for a non-periodic pattern;
  • O (n / m) best performance.

BM.h file

# include <iostream>
# include <string.h>
using namespace std;

int bmsearch(char *text,char *pat,int *no,int *pos)
	int i,table[256];
	int len=strlen(pat);
	int compcount=0;
	int patcount=len-1;
		int count=0;
			else count++;
	return compcount;

BMTest.cpp File

# include "bm.h"
# include <conio.h>
# include <stdio.h>
using namespace std;

	char text[300],pat[100];
	int no,count,pos[20],i;
	cout<<"\n\nEnter the text string:";
	cout<<"Enter the pattern string:";
	cout<<"\n\nPattern string occoured "<<no<<" times.";
	cout<<"\n"<<count<<" comparisons required";
	cout<<"\nPositions of occourence:\n";
	cout<<" Bye Bye.";
	return 0;
Tagged with: C/C++ languageSource Code

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>


Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Related News Feeds

Set your Twitter account name in your settings to use the TwitterBar Section.