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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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