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
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

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

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

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

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

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

Here is the call graph for this function:

main()

int main

(

void

)

Main Function that calls test function.

Returns

0 on exit

          {
    test();
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Function with test cases for Horspool's algorithm.

Returns

void

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