pastebin

Paste Search Dynamic
Recent pastes
badCharHeuristic
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. # define Total_Chars 256
  5.  
  6. // The preprocessing function
  7. void badCharHeuristic(string str, int size, int bad_characters[Total_Chars]) {
  8.   int i;
  9.   // Initialize with -1
  10.   for (i = 0; i < Total_Chars; i++)
  11.     bad_characters[i] = -1;
  12.  
  13.   // Fill the actual value of last occurrence
  14.   // of a character
  15.   for (i = 0; i < size; i++) {
  16.     bad_characters[(int) str[i]] = i;
  17.   }
  18. }
  19.  
  20. // Boyer Moore algorithm using bad character Heuristic
  21. void boyermoore(string T, string P) {
  22.   int m = P.size();
  23.   int n = T.size();
  24.  
  25.   int bad_character[Total_Chars];
  26.  
  27.   /* Preprocessing function to  fill the bad character array */
  28.   badCharHeuristic(P, m, bad_character);
  29.  
  30.   int idx = 0; /* idx defines how much pattern is shifted */
  31.   while (idx <= (n - m)) {
  32.     int j = m - 1;
  33.  
  34.     /* Reducing j of P until we gets a
  35.     mismatch character, at this shift idx */
  36.     while (j >= 0 && P[j] == T[idx + j])
  37.       j--;
  38.  
  39.     /* In case if we get j=-1 which signify that
  40.     P is present at current shift */
  41.     if (j < 0) {
  42.       cout << "Shift at which pattern occurs = " << idx << "n";
  43.  
  44.       /* We will shift P such that the next
  45.         character in T aligns with the last
  46.         occurrence of it in P.
  47.         To cover the case when P occur at end
  48.         of T we need the condition idx+m < n */
  49.  
  50.       idx += (idx + m < n) ? m - bad_character[T[idx + m]] : 1;
  51.     }
  52.     // other case
  53.     else
  54.       /* In this case also, We will shift P such
  55.         that the next character in T aligns
  56.         with the last occurrence of it in P.
  57.         To unsure that we get positive
  58.         shift we are using max function.
  59.         The negative shift may occur when the
  60.         last occurrence of bad character in P
  61.         is on the right side of the current
  62.         character. */
  63.  
  64.       idx += max(1, j - bad_character[T[idx + j]]);
  65.   }
  66. }
  67.  
  68. int main() {
  69.   string text = "AYRRQMGRPCRQ";
  70.   string pattern = "RPCRQ";
  71.   boyermoore(text, pattern);
  72.   return 0;
  73. }
Parsed in 0.020 seconds