Demonstration of Boyer Moore Algorithm for string matching.

boyermoore.cpp

#include <iostream>
#include <cstring>
#include <fstream>
#include <map>

int main(void){
    std::string text;
    std::string pattern;

    // Read the text from the file.
    /*
    std::ifstream myFile;
    myFile.open("outfile.txt", std::ios::in);
    while(!myFile.eof()){
        std::string temp;
        std::getline(myFile, temp);
        text += temp;
    }
    */
    getline(std::cin, text);
    // Input the pattern manually :D
    getline(std::cin, pattern);
    
    // Construct the bad match table:
    // Use a hash match for the bad match table.
    std::map<char, int> positionEncoding;   // Stores the Bad match hopping distance of the characters.
    for(int i=0; i<pattern.size(); i++){
        char ch = pattern[i];
        int position = pattern.size() - i - 1;
        positionEncoding[ch] = position;
    }
    for(std::pair<char, int> p:positionEncoding){
        std::cout << p.first << " : " << p.second << std::endl;
    }
    // Completed making the pattern.
    std::cout << "Comparing " << text << " with " << pattern << std::endl;
    std::cout << "==========" << std::endl;
    bool found = false;
    int total = 0;
    for(int i=0; i<text.size(); ){
        // i denotes the current position in the text source to be matched.
            total++;            

        bool flag = true;
        int jval = 0;
        for(int j = (pattern.size() - 1) ; j >= 0; j--){
            std::cout << "i is: " << i << " and j is: " << j << std::endl;
            std::cout << "Comparing position [" << i+j << "] in text : " << text[i+j];
            std::cout << " With pattern [" << j << "] " << pattern[j] << std::endl;
            if(pattern[j] == text[i+j]){
                std::cout << "MATCH" << std::endl;
                flag = true;
                std::cout << "----------" << std::endl;
                continue;
            }
            else{
                std::cout << "MISMATCH" << std::endl;
                flag = false;
                // get current mismatched char.
                char ch = text[i+j];
                std::cout << "Position encoding of mismatched character: " << ch << " is " << positionEncoding[ch] << std::endl;
                jval = j;
                break;
            }
        }
        if(flag){
            std::cout << "Found pattern at: " << i << std::endl;
            std::cout << "Total Comparisions required for matching the character : " << total << std::endl;
            found = true;
            break;
        }
        else{
            std::cout << "Finding position " << i << " failed. " << std::endl;
            std::cout << "New position of i is: ";
            i += positionEncoding[text[i+jval]] != 0 ? positionEncoding[text[i+jval]] : pattern.size();
            std::cout << i << std::endl;
            char ch = text[i+jval];
            std::cout << "Mismatched character is: " << ch << std::endl;
            std::cout << "------------" << std::endl;
        }
    }
    if(!found){
        std::cout << "Could not find the pattern. " << std::endl;
        std::cout << "Total Comparisions required for matching the character : " << total << std::endl;
    }
    return 0;
}