fork(8) download 
  1. /* Program for Bad Character Heuristic of Boyer Moore String Matching Algorithm */
  2.  
  3. # include <limits.h>
  4. # include <string.h>
  5. # include <stdio.h>
  6.  
  7. # define NO_OF_CHARS 256
  8.  
  9. // A utility function to get maximum of two integers
  10. int max (int a, int b) { return (a > b)? a: b; }
  11.  
  12. // The preprocessing function for Boyer Moore's bad character heuristic
  13. void badCharHeuristic( char *str, int size, int badchar[NO_OF_CHARS])
  14. {
  15.     int i;
  16.  
  17.     // Initialize all occurrences as -1
  18.     for (i = 0; i < NO_OF_CHARS; i++)
  19.          badchar[i] = -1;
  20.  
  21.     // Fill the actual value of last occurrence of a character
  22.     for (i = 0; i < size; i++)
  23.          badchar[(int) str[i]] = i;
  24. }
  25.  
  26. /* A pattern searching function that uses Bad Character Heuristic of
  27.    Boyer Moore Algorithm */
  28. void search( char *txt,  char *pat)
  29. {
  30.     int m = strlen(pat);
  31.     int n = strlen(txt);
  32.  
  33.     int badchar[NO_OF_CHARS];
  34.  
  35.     /* Fill the bad character array by calling the preprocessing
  36.        function badCharHeuristic() for given pattern */
  37.     badCharHeuristic(pat, m, badchar);
  38.  
  39.     int s = 0;  // s is shift of the pattern with respect to text
  40.     while(s <= (n - m))
  41.     {
  42.         int j = m-1;
  43.  
  44.         /* Keep reducing index j of pattern while characters of
  45.            pattern and text are matching at this shift s */
  46.         while(j >= 0 && pat[j] == txt[s+j])
  47.             j--;
  48.  
  49.         /* If the pattern is present at current shift, then index j
  50.            will become -1 after the above loop */
  51.         if (j < 0)
  52.         {
  53.             printf("\n pattern occurs at shift = %d", s);
  54.  
  55.             /* Shift the pattern so that the next character in text
  56.                aligns with the last occurrence of it in pattern.
  57.                The condition s+m < n is necessary for the case when
  58.                pattern occurs at the end of text */
  59.             s += (s+m < n)? m-badchar[txt[s+m]] : 1;
  60.  
  61.         }
  62.  
  63.         else
  64.             /* Shift the pattern so that the bad character in text
  65.                aligns with the last occurrence of it in pattern. The
  66.                max function is used to make sure that we get a positive
  67.                shift. We may get a negative shift if the last occurrence
  68.                of bad character in pattern is on the right side of the
  69.                current character. */
  70.             s += max(1, j - badchar[txt[s+j]]);
  71.     }
  72. }
  73.  
  74. /* Driver program to test above funtion */
  75. int main()
  76. {
  77.     char txt[] = "ABAAAABAACD";
  78.     char pat[] = "AA";
  79.     search(txt, pat);
  80.     return 0;
  81. }
  82.  
Success #stdin #stdout 0s 2292KB
comments (?)
stdin 
Standard input is empty
stdout 
 pattern occurs at shift = 2
 pattern occurs at shift = 3
 pattern occurs at shift = 4
 pattern occurs at shift = 7
https://ideone.com/FhJok5
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!