{"id":25500,"date":"2017-10-25T19:53:20","date_gmt":"2017-10-25T14:23:20","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25500"},"modified":"2017-10-25T19:53:20","modified_gmt":"2017-10-25T14:23:20","slug":"c-programming-for-pattern-searching-set-7-boyer-moore-algorithm-bad-character-heuristic","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-for-pattern-searching-set-7-boyer-moore-algorithm-bad-character-heuristic\/","title":{"rendered":"C++ programming for Pattern Searching Set 7 Boyer Moore Algorithm \u2013 Bad Character Heuristic"},"content":{"rendered":"

Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.<\/span><\/p>\n

Examples:<\/p>\n

Input:  txt[] = \"THIS IS A TEST TEXT\"\r\n        pat[] = \"TEST\"\r\nOutput: Pattern found at index 10\r\n\r\nInput:  txt[] =  \"AABAACAADAABAABA\"\r\n        pat[] =  \"AABA\"\r\nOutput: Pattern found at index 0\r\n        Pattern found at index 9\r\n        Pattern found at index 12\r\n\"C++<\/pre>\n
Pattern searching is an important problem in computer science. When we do search for a string in notepad\/word file or browser or database, pattern searching algorithms are used to show the search results.<\/p>\n[ad type=”banner”]\n
We have discussed the following algorithms in the previous posts:<\/p>\n
Naive Algorithm
\nKMP Algorithm
\nRabin Karp Algorithm
\nFinite Automata based Algorithm<\/p>\n
In this post, we will discuss Boyer Moore pattern searching algorithm. Like KMP and Finite Automata algorithms, Boyer Moore algorithm also preprocesses the pattern.
\nBoyer Moore is a combination of following two approaches.
\n1) Bad Character Heuristic
\n2) Good Suffix Heuristic
\nBoth of the above heuristics can also be used independently to search a pattern in a text. Let us first understand how two independent approaches work together in the Boyer Moore algorithm. If we take a look at the Naive algorithm, it slides the pattern over the text one by one. KMP algorithm does preprocessing over the pattern so that the pattern can be shifted by more than one. The Boyer Moore algorithm does preprocessing for the same reason. It preporcesses the pattern and creates different arrays for both heuristics. At every step, it slides the pattern by max of the slides suggested by the two heuristics. So it uses best of the two heuristics at every step. Unlike the previous pattern searching algorithms, Boyer Moore algorithm starts matching from the last character of the pattern.<\/p>\n[ad type=”banner”]\n
In this post, we will discuss bad character heuristic, and discuss Good Suffix heuristic in the next post.<\/p>\n
The idea of bad character heuristic is simple. The character of the text which doesn\u2019t match with the current character of pattern is called the Bad Character. Whenever a character doesn\u2019t 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.<\/p>\n
 
 C++<\/span> <\/div> 
\/* 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 integersint max (int a, int b) { return (a > b)? a: b; } \/\/ The preprocessing function for Boyer Moore's bad character heuristicvoid 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;} \/* A pattern searching function that uses Bad Character Heuristic of   Boyer Moore Algorithm *\/void search( char *txt,  char *pat){    int m = strlen(pat);    int n = strlen(txt);     int badchar[NO_OF_CHARS];     \/* Fill the bad character array by calling the preprocessing       function badCharHeuristic() for given pattern *\/    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;         \/* Keep reducing index j of pattern while characters of           pattern and text are matching at this shift s *\/        while(j >= 0 && pat[j] == txt[s+j])            j--;         \/* If the pattern is present at current shift, then index j           will become -1 after the above loop *\/        if (j < 0)        {            printf("\\n pattern occurs at shift = %d", s);             \/* Shift the pattern so that the next character in text               aligns with the last occurrence of it in pattern.               The condition s+m < n is necessary for the case when               pattern occurs at the end of text *\/            s += (s+m < n)? m-badchar[txt[s+m]] : 1;         }         else            \/* Shift the pattern so that the bad character in text               aligns with the last occurrence of it in pattern. The               max function is used to make sure that we get a positive               shift. We may get a negative shift if the last occurrence               of bad character in pattern is on the right side of the               current character. *\/            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;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
pattern occurs at shift = 4
\nThe Bad Character Heuristic may take O(mn) time in worst case. The worst case occurs when all characters of the text and pattern are same. For example, txt[] = \u201cAAAAAAAAAAAAAAAAAA\u201d and pat[] = \u201cAAAAA\u201d.<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
C++ programming for Pattern Searching Set 7 Boyer Moore Algorithm \u2013 Bad Character Heuristic – Searching and Sorting – When we do search for a string in file.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515,1,83558,71670],"tags":[71314,73383,73273,73385,73609,73321,73300,73320,73322,73596,7378,73594,70706,73603,73599,73388,73591,73606,73595,73605,73598,73282,73194,73283,73270,73600,73279,73296,73604,73602,73274,73281,73588,73601,73264,73597,70272,70315,73184,73299,73287,73316,73271,73592,73607,73608,73275,73593,73276,73293],"class_list":["post-25500","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-coding","category-moore-algorithm","category-searching-and-sorting","tag-algorithm-in-c","tag-alphabet-pattern-programs-in-c","tag-best-pattern-matching-algorithm","tag-best-searching-algorithm-in-c","tag-boyer-moore-algorithm-c-code","tag-boyer-moore-algorithm-example","tag-boyer-moore-algorithm-explanation","tag-boyer-moore-pattern-matching-algorithm","tag-boyer-moore-pattern-matching-algorithm-example","tag-boyer-moore-program-in-c","tag-c-string","tag-cmore","tag-design-and-analysis-of-algorithms-ppt","tag-dna-matching-algorithm","tag-dna-pattern-matching","tag-dna-pattern-matching-algorithm","tag-example-of-brute-force-algorithm","tag-fast-bowel-movement","tag-fast-search","tag-fast-strings","tag-faststring","tag-first-pattern-matching-algorithm","tag-kmp-algorithm","tag-kmp-algorithm-explained","tag-pattern-matching-algorithm","tag-pattern-matching-algorithm-for-intrusion-detection-system","tag-pattern-matching-algorithm-in-c","tag-pattern-matching-algorithm-in-data-structure","tag-pattern-matching-algorithm-in-data-structure-ppt","tag-pattern-matching-algorithm-in-image-processing","tag-pattern-matching-algorithm-ppt","tag-pattern-matching-ppt","tag-python-string-substring","tag-quick-search-match","tag-rabin-karp-algorithm-code-in-c","tag-ruby-string","tag-search-algorithms","tag-searching-algorithms-in-java","tag-string-algorithms","tag-string-algorithms-pdf","tag-string-pattern-matching-algorithms","tag-string-pattern-programs-in-c","tag-strstr-implementation-in-c","tag-strstr-in-c","tag-substring-swift","tag-text-bm","tag-text-comparison-algorithm","tag-what-is-algorithm-in-c","tag-what-is-pattern-matching-algorithm","tag-word-matching-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25500","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25500"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25500\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25500"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25500"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25500"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}