horspool.cpp

Go to the documentation of this file.

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

namespace strings {
namespace horspool {
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;
}

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

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

int main(){
    test();
    return 0;
}