Skip to content

Instantly share code, notes, and snippets.

@loosechainsaw
Created August 20, 2015 15:05
Show Gist options
  • Save loosechainsaw/691eca9d8a51de4f7f50 to your computer and use it in GitHub Desktop.
Save loosechainsaw/691eca9d8a51de4f7f50 to your computer and use it in GitHub Desktop.
#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;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment