1

На просторах инета нашел лишь один полный (где есть оба правила: хороший суффикс и плохой символ) алгоритм.
Остальные или используют чистые 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]
1
  • Собственно, почему эта проблема возникает и как ее устранить?
    – SlimRG
    31 мар 2020 в 18:11

1 ответ 1

2

Я думаю, ваше условие неправильно написано... Должно быть

for ( ; i >= 0; --i)

вместо for ( ; i != 0; --i)

1
  • 1
    Место вы указали правильно, а вот size_t не учли. Решил проблему заменой i на i+1
    – SlimRG
    31 мар 2020 в 19:38

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.