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:

Go to the source code of this file.

Namespaces
namespace	strings
	String algorithms.
namespace	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.
int	main ()
	Main Function that calls test function.

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

Definition in file horspool.cpp.

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

prototype

is the substring that we use to find shift table

Returns

Shift Table of Horspool's algorithm

Definition at line 26 of file horspool.cpp.

                                                                       {
    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;
}

horspool()

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

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

Definition at line 59 of file horspool.cpp.

                                                                 {
    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;
}

main()

int main

(

void

)

Main Function that calls test function.

Returns

0 on exit

Definition at line 119 of file horspool.cpp.

          {
    test();
    return 0;
}

test()

static void test ( )

static

Function with test cases for Horspool's algorithm.

Returns

void

Definition at line 100 of file horspool.cpp.

                  {
    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);
}