Horspool's algorithm that finds if a string contains a substring (https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm)
More...
#include <iostream>
#include <unordered_map>
#include <cassert>
◆ findShiftTable()
A function that finds the shift table of the given prototype string that we need in Horpool's algorithm.
- Parameters
-
prototype | is the substring that we use to find shift table |
- Returns
- Shift Table of Horspool's algorithm
30 for (
int i = 0; i < prototype.
size();
32 if (shiftTable.
find(prototype[i]) ==
34 if (i != prototype.
size() - 1) {
36 prototype[i], prototype.
size() - i -
44 if (i != prototype.
size() - 1) {
45 shiftTable[prototype[i]] = prototype.
size() - i - 1;
◆ horspool()
A function that implements Horspool's algorithm.
- Parameters
-
text | is the string that we are searching if there is a substring |
prototype | is the substring that we are searching in text |
- Returns
- true if text string contains prototype string
-
false if text string does not contain prototype string
63 int i =
static_cast<int>(
66 while (i < text.
size()) {
70 for (
int z =
static_cast<int>(prototype.
size() - 1); z >= 0 && flag;
72 if (text[j] == prototype[z]) {
84 if (shiftTable.
find(text[i]) != shiftTable.
end()) {
85 i += shiftTable[text[i]];
87 i += prototype.
size();
◆ main()
Main Function that calls test function.
- Returns
- 0 on exit
◆ test()
Function with test cases for Horspool's algorithm.
- Returns
- void
101 assert(strings::horspool::horspool(
"Hello World",
"World") ==
true);
102 assert(strings::horspool::horspool(
"Hello World",
" World") ==
true);
103 assert(strings::horspool::horspool(
"Hello World",
"ello") ==
true);
104 assert(strings::horspool::horspool(
"Hello World",
"rld") ==
true);
105 assert(strings::horspool::horspool(
"Hello",
"Helo") ==
false);
106 assert(strings::horspool::horspool(
"c++_algorithms",
"c++_algorithms") ==
true);
107 assert(strings::horspool::horspool(
"c++_algorithms",
"c++_") ==
true);
108 assert(strings::horspool::horspool(
"Hello",
"Hello World") ==
false);
109 assert(strings::horspool::horspool(
"c++_algorithms",
"") ==
false);
110 assert(strings::horspool::horspool(
"c++",
"c") ==
true);
111 assert(strings::horspool::horspool(
"3458934793",
"4793") ==
true);
112 assert(strings::horspool::horspool(
"3458934793",
"123") ==
false);