C Program
#include <stdio.h>
#include <string.h>
#define NO_OF_CHARS 256
void badCharHeuristic(char *str, int size, int badchar[NO_OF_CHARS]) {
for (int i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
for (int 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;
while (s <= (n - m)) {
int j = m - 1;
while (j >= 0 && pat[j] == txt[s + j])
j--;
if (j < 0) {
printf("Pattern occurs at index %d\n", s);
s += (s + m < n) ? m - badchar[(int)txt[s + m]] : 1;
} else {
s += (j - badchar[(int)txt[s + j]] > 1) ? j - badchar[(int)txt[s + j]] : 1;
}
}
}
int main() {
char txt[] = "ABAAABCD";
char pat[] = "ABC";
search(txt, pat);
return 0;
}C Output
Pattern occurs at index 4
C++ Program
#include <iostream>
#include <string>
using namespace std;
#define NO_OF_CHARS 256
void badCharHeuristic(string str, int size, int badchar[NO_OF_CHARS]) {
for (int i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
for (int i = 0; i < size; i++)
badchar[(int)str[i]] = i;
}
void search(string txt, string pat) {
int m = pat.size();
int n = txt.size();
int badchar[NO_OF_CHARS];
badCharHeuristic(pat, m, badchar);
int s = 0;
while (s <= (n - m)) {
int j = m - 1;
while (j >= 0 && pat[j] == txt[s + j])
j--;
if (j < 0) {
cout << "Pattern occurs at index " << s << endl;
s += (s + m < n) ? m - badchar[txt[s + m]] : 1;
} else {
s += max(1, j - badchar[txt[s + j]]);
}
}
}
int main() {
string txt = "ABAAABCD";
string pat = "ABC";
search(txt, pat);
return 0;
}C++ Output
Pattern occurs at index 4
JAVA Program
public class BoyerMoore {
static final int NO_OF_CHARS = 256;
static void badCharHeuristic(char[] str, int size, int badchar[]) {
for (int i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
for (int i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
static void search(String txt, String pat) {
int m = pat.length();
int n = txt.length();
int[] badchar = new int[NO_OF_CHARS];
badCharHeuristic(pat.toCharArray(), m, badchar);
int s = 0;
while (s <= (n - m)) {
int j = m - 1;
while (j >= 0 && pat.charAt(j) == txt.charAt(s + j))
j--;
if (j < 0) {
System.out.println("Pattern occurs at index " + s);
s += (s + m < n) ? m - badchar[txt.charAt(s + m)] : 1;
} else {
s += Math.max(1, j - badchar[txt.charAt(s + j)]);
}
}
}
public static void main(String[] args) {
String txt = "ABAAABCD";
String pat = "ABC";
search(txt, pat);
}
}JAVA Output
Pattern occurs at index 4
Python Program
def badCharHeuristic(string, size):
badChar = [-1] * 256
for i in range(size):
badChar[ord(string[i])] = i
return badChar
def search(txt, pat):
m = len(pat)
n = len(txt)
badChar = badCharHeuristic(pat, m)
s = 0
while s <= n - m:
j = m - 1
while j >= 0 and pat[j] == txt[s + j]:
j -= 1
if j < 0:
print("Pattern occurs at index", s)
s += m - badChar[ord(txt[s + m])] if s + m < n else 1
else:
s += max(1, j - badChar[ord(txt[s + j])])
txt = "ABAAABCD"
pat = "ABC"
search(txt, pat)Python Output
Pattern occurs at index 4
Explanation
Example
Boyer-Moore algorithm is the most effective string searching algorithm. For example, if we are searching for "ABC" in "ABAAABCD", rather than scanning each character sequentially like the naive approach, it employs sophisticated shifting rules to advance by skipping, rapidly locating the pattern at position 4.
Real-Life Analogy
Suppose you're scanning through a book looking for the word "DATA". You don't read each letter in each word, but rather look ahead and skip entire segments if the last letter isn't right. That's precisely what Boyer-Moore does—it scans mismatches intelligently and determines how far it can skip forward without losing the pattern.
Why It Matters
Boyer-Moore is one of the fastest known pattern matching algorithms, particularly for pattern matching in large text. The reason it's so efficient is because it's based on two rules: bad character rule (in case of a mismatch, skip according to mismatched character) and good suffix rule (shift pattern in order to match previously matched suffix). For most real-world applications such as text editors, DNA sequence search, and spam blocking, this algorithm significantly diminishes the number of comparisons.
Learning Insights
Learning Boyer-Moore shows you the way preprocessing can streamline efficiency. In contrast to brute-force algorithms that always advance one step at a time, Boyer-Moore "looks ahead" with pre-knowledge of the pattern. This presents the concept of heuristics and how they can inform efficient search strategies. It also solidifies string manipulation and array indexing concepts, which are crucial in competitive programming and tech interviews.
Interview and Project Use
Boyer-Moore is usually asked after naive string search or the Knuth-Morris-Pratt (KMP) algorithm in interviews. To know its operation indicates that you are aware of sophisticated search methods and know how to optimize algorithms to real-world size. For tasks such as search engines, data mining, plagiarism detection tools, and antivirus systems, Boyer-Moore's performance lead can be very significant when searching millions of characters.
In computer science and programming, knowing the Boyer-Moore algorithm is akin to being an expert at the intelligent shortcut of searching wisely. It avoids unnecessary steps, making it much more efficient than naive methods. This is the reason why it's commonly used in text processing, file searching, and bioinformatics software. Beginners should practice this algorithm because it combines logic, pattern analysis, and optimization, which are key skills in coding interviews and real-world software engineering. By learning Boyer-Moore, you’re not just solving a search problem—you’re learning how to approach programming challenges with smarter strategies that scale.
Social Plugin