Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
horspool.cpp File Reference

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>
Include dependency graph for horspool.cpp:

Namespaces

 strings
 Algorithms with strings.
 
 horspool
 Functions for Horspool's algorithm.
 

Functions

std::unordered_map< char, int > strings::horspool::findShiftTable (const std::string &prototype)
 
bool strings::horspool::horspool (const std::string &text, const std::string &prototype)
 
static void test ()
 Function with test cases for Horspool's algorithm. More...
 
int main ()
 Main Function that calls test function. More...
 

Detailed Description

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

Function Documentation

◆ findShiftTable()

std::unordered_map<char, int> strings::horspool::findShiftTable ( const std::string prototype)

A function that finds the shift table of the given prototype string that we need in Horpool's algorithm.

Parameters
prototypeis the substring that we use to find shift table
Returns
Shift Table of Horspool's algorithm
26  {
28  shiftTable; // A HashMap for shift table that has characters for keys and integers for values
29 
30  for (int i = 0; i < prototype.size();
31  i++) { // Checking all characters of prototype string
32  if (shiftTable.find(prototype[i]) ==
33  shiftTable.end()) { // If character does not exist in HashMap
34  if (i != prototype.size() - 1) {
35  shiftTable.insert(std::make_pair(
36  prototype[i], prototype.size() - i -
37  1)); // Insert the character as key and the size of prototype string - index of character - 1 as value
38  } else {
39  shiftTable.insert(std::make_pair(
40  prototype[i],
41  prototype.size())); // Insert the character as key and the size of prototype string as value
42  }
43  } else {
44  if (i != prototype.size() - 1) {
45  shiftTable[prototype[i]] = prototype.size() - i - 1;
46  }
47  }
48  }
49  return shiftTable;
50 }
Here is the call graph for this function:

◆ horspool()

bool strings::horspool::horspool ( const std::string text,
const std::string prototype 
)

A function that implements Horspool's algorithm.

Parameters
textis the string that we are searching if there is a substring
prototypeis 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
59  {
61  prototype); // Initialise shift table calling findShiftTable function
62 
63  int i = static_cast<int>(
64  prototype.size() -
65  1); // Index that we shift in text to find the substring
66  while (i < text.size()) {
67  int j = i, k = 0;
68  bool flag = true;
69 
70  for (int z = static_cast<int>(prototype.size() - 1); z >= 0 && flag;
71  z--) { // Checking if all characters of substring are equal with all characters of string
72  if (text[j] == prototype[z]) {
73  k++;
74  j--;
75  } else {
76  flag = false; // If two characters are not equal set flag to false and break from loop
77  }
78  }
79 
80  if (k ==
81  prototype.size()) { // If all characters match then return true
82  return true;
83  } else {
84  if (shiftTable.find(text[i]) != shiftTable.end()) {
85  i += shiftTable[text[i]]; // If shift table contains the character then shift index as many steps as value
86  } else {
87  i += prototype.size(); // If character does not exist in shift table then shift index as many steps as size of prototype string
88  }
89  }
90  }
91  return false;
92 }
Here is the call graph for this function:

◆ main()

int main ( void  )

Main Function that calls test function.

Returns
0 on exit
119  {
120  test();
121  return 0;
122 }
Here is the call graph for this function:

◆ test()

static void test ( )
static

Function with test cases for Horspool's algorithm.

Returns
void
100  {
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);
113 }
std::unordered_map::find
T find(T... args)
std::string::size
T size(T... args)
test
static void test()
Function with test cases for Horspool's algorithm.
Definition: horspool.cpp:100
std::unordered_map::insert
T insert(T... args)
std::make_pair
T make_pair(T... args)
std::unordered_map::end
T end(T... args)
std::unordered_map
STL class.
strings::horspool::findShiftTable
std::unordered_map< char, int > findShiftTable(const std::string &prototype)
Definition: horspool.cpp:26