Horspool

G
```/**
* @file
* @brief Horspool's algorithm that finds if a string contains a substring (https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm)
* @author [Harry Kontakis](https://github.com/ckontakis)
*/

#include <iostream>
#include <unordered_map>
#include <cassert>

/**
* @namespace strings
* @brief Algorithms with strings
*/
namespace strings {
/**
* @namespace horspool
* @brief Functions for [Horspool's](https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm) algorithm
*/
namespace horspool {
/**
* A function that finds the shift table of the given prototype string that we need in Horpool's algorithm.
* @param prototype is the substring that we use to find shift table
* @return Shift Table of Horspool's algorithm
*/
std::unordered_map<char, int> findShiftTable(const std::string &prototype) {
std::unordered_map<char, int>
shiftTable;  // A HashMap for shift table that has characters for keys and integers for values

for (int i = 0; i < prototype.size();
i++) {  // Checking all characters of prototype string
if (shiftTable.find(prototype[i]) ==
shiftTable.end()) {  // If character does not exist in HashMap
if (i != prototype.size() - 1) {
shiftTable.insert(std::make_pair(
prototype[i], prototype.size() - i -
1));  // Insert the character as key and the size of prototype string - index of character - 1 as value
} else {
shiftTable.insert(std::make_pair(
prototype[i],
prototype.size()));  // Insert the character as key and the size of prototype string as value
}
} else {
if (i != prototype.size() - 1) {
shiftTable[prototype[i]] = prototype.size() - i - 1;
}
}
}
return shiftTable;
}

/**
* A function that implements Horspool's algorithm.
* @param text is the string that we are searching if there is a substring
* @param prototype is the substring that we are searching in text
* @returns true if text string contains prototype string
* @returns false if text string does not contain prototype string
*/
bool horspool(const std::string &text, const std::string &prototype) {
std::unordered_map<char, int> shiftTable = findShiftTable(
prototype);  // Initialise shift table calling findShiftTable function

int i = static_cast<int>(
prototype.size() -
1);  // Index that we shift in text to find the substring
while (i < text.size()) {
int j = i, k = 0;
bool flag = true;

for (int z = static_cast<int>(prototype.size() - 1); z >= 0 && flag;
z--) {  // Checking if all characters of substring are equal with all characters of string
if (text[j] == prototype[z]) {
k++;
j--;
} else {
flag = false;  // If two characters are not equal set flag to false and break from loop
}
}

if (k ==
prototype.size()) {  // If all characters match then return true
return true;
} else {
if (shiftTable.find(text[i]) != shiftTable.end()) {
i += shiftTable[text[i]];  // If shift table contains the character then shift index as many steps as value
} else {
i += prototype.size();  // If character does not exist in shift table then shift index as many steps as size of prototype string
}
}
}
return false;
}
} // namespace horspool
} // namespace strings

/**
* @brief Function with test cases for Horspool's algorithm
* @returns void
*/
static void test(){
assert(strings::horspool::horspool("Hello World","World") == true);
assert(strings::horspool::horspool("Hello World"," World") == true);
assert(strings::horspool::horspool("Hello World","ello") == true);
assert(strings::horspool::horspool("Hello World","rld") == true);
assert(strings::horspool::horspool("Hello","Helo") == false);
assert(strings::horspool::horspool("c++_algorithms","c++_algorithms") == true);
assert(strings::horspool::horspool("c++_algorithms","c++_") == true);
assert(strings::horspool::horspool("Hello","Hello World") == false);
assert(strings::horspool::horspool("c++_algorithms","") == false);
assert(strings::horspool::horspool("c++","c") == true);
assert(strings::horspool::horspool("3458934793","4793") == true);
assert(strings::horspool::horspool("3458934793","123") == false);
}

/**
* @brief Main Function that calls test function
* @returns 0 on exit
*/
int main(){
test();
return 0;
}
```