boyermoore.cpp

#include <iostream>

using namespace std;

namespace search {
    namespace algorithms {
        long boyer_moore(std::string const &text, std::string const &pattern) {

            auto m = pattern.size();
            auto n = text.size();
            decltype(m) right[256];

            for(int i = 0; i < 256; ++i){
                right[i] = 0;
            }

            for(decltype(m) i = 0; i < m; ++i){
                right[pattern[i]] = i;
            }

            decltype(m) skip = 0;
            for(decltype(m) i = 0; i <= n - m; i += skip){

                skip = 0;

                for(int j = m - 1; j > 0; --j){
                    if(pattern[j] != text[i + j]){
                        skip = std::max(1UL,j - right[text[i + j]]);
                        cout << "Skip" <<  skip << endl;
                        break;
                    }
                }

                if(skip == 0)
                    return i;
            }
            return -1;
        }
    }
}