На просторах инета нашел лишь один полный (где есть оба правила: хороший суффикс и плохой символ) алгоритм.
Остальные или используют чистые C или не используют всех правил...
Ссылка на него: GitHub
Вот он:
bm.cpp
#include "bm.h"
boyerMoore::boyerMoore(const string& s) {
needle = s;
goodSuffixVec(s, gsv);
return;
}
void boyerMoore::goodSuffixVec(const string& s, vector<int>& v) {
size_t np = s.size();
v.resize(np, -1);
for (size_t r = np - 1; r > 0; --r) {
size_t nn = np - r;
size_t nsub = string::npos;
size_t gm;
string sstr = s.substr(r);
if((nsub = s.rfind(sstr, r - 1)) == string::npos) {
for (int i = 1; i != np - r; ++i) {
if (strncmp(s.c_str(), sstr.c_str() + np - r - i, i) == 0) {
v[r] = np - 1;
continue;
}
}
if (v[r] != -1) {
continue;
}
v[r] = np - 1 - (-1);
} else {
v[r] = np - 1 - (nsub + nn - 1);
}
}
}
ssize_t boyerMoore::crfind(const string& str, const char c, size_t pos) {
if (str.size() < pos + 1) {
return -1;
}
for (int i = pos; i >= 0; --i) {
if (str[i] == c) {
return i;
}
}
return -1;
}
bool boyerMoore::bmC(const string& haystack) {
size_t index(0);
size_t np = needle.size();
size_t nh = haystack.size();
size_t i = np - 1;
for ( ; i != 0; --i) {
if (needle[i] == haystack[index + i]) {
continue;
} else {
ssize_t bad_pos = crfind(needle, haystack[index + i], i - 1);
size_t bad_move = i - bad_pos;
size_t good_move = i + 1 >= np ? 0 : gsv[i + 1];
index += max(bad_move, good_move);
if (index + np - 1 > nh) {
return false;
}
i = np;
}
}
if (i == 0) {
return true;
}
return false;
}
bm.h
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <fstream>
#include <iterator>
using namespace std;
class boyerMoore {
private:
string needle;
vector<int> gsv;
void goodSuffixVec(const string& s, vector<int> &v);
ssize_t crfind(const string& str, const char c, size_t pos);
public:
boyerMoore(const string& needle);
bool bmC(const string& haystack);
};
main.cpp
#include <iostream>
#include "bm.h"
using namespace std;
int main()
{
boyerMoore bm("0SSIP");
cout << bm.bmC("MISSISSIPPI") << endl;
return 0;
}
Программа работает верно, вроде проблем нет, за исключением одного НО!
Программа игнорирует первый символ подстроки
Примеры работы:
[Text:Pattern:Result]
[MISSISSIPPI:0MISSISSIPPI:false]
[MISSISSIPPI:0ISSISSIPPI:true]
[MISSISSIPPI:ISSIP:true]
[MISSISSIPPI:0ISSIP:true]
[MISSISSIPPI:IS0IP:false]
[MISSISSIPPI:IS0IP:false]