pastebin

Paste Search Dynamic
Recent pastes
1. #include <bits/stdc++.h>
2.
3. using namespace std;
4. # define Total_Chars 256
5.
6. // The preprocessing function
8.   int i;
9.   // Initialize with -1
10.   for (i = 0; i < Total_Chars; i++)
12.
13.   // Fill the actual value of last occurrence
14.   // of a character
15.   for (i = 0; i < size; 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.
26.
27.   /* Preprocessing function to  fill the bad character array */
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