Repository: TheAlgorithms/C-Plus-Plus
File: strings/boyer_moore.cpp (C++)

Code before:
 * @brief Check if pat is prefix of str.
 * 
 * @param str pointer to some part of the input text.
 * @param pat the searched pattern.
 * @param len length of the searched pattern
 * @return true if pat is prefix of str. false otherwise.
 */
bool is_prefix(const char* str, const char* pat, size_t len) {
    if (strlen(str) < len)
        return false;

    for (size_t i = 0; i < len; i++)
        if (str[i] != pat[i])
            return false;

    return true;
}

void and_test(const char* text) {
    pattern ands;
    init_pattern("and", ands);
    std::vector<size_t> indexes = search(text, ands);

    assert(indexes.size() == 2);
    assert(is_prefix(text + indexes[0], "and", 3));
    assert(is_prefix(text + indexes[1], "and", 3));
}

void pat_test(const char* text) {
    pattern pat;
    init_pattern("pat", pat);
    std::vector<size_t> indexes = search(text, pat);

    assert(indexes.size() == 6);

    for (const auto& idx : indexes) {
        assert(is_prefix(text + idx, "pat", 3));
    }
}
/**
 * @brief Self-test implementations
 * @return void
 */
static void tests() {
    const char* text =
        "When pat Mr. and Mrs. pat Dursley woke up on the dull, gray  \
                            Tuesday our story starts, \
                there was nothing about pat the cloudy sky outside to pat suggest that\
                        strange and \
                    mysterious things would pat soon be happening all pat over the \
                        country.";

Review comment (suggestion):
```suggestion
    assert(strings::boyer_moore::is_prefix(text + indexes[0], "and", 3));
    assert(strings::boyer_moore::is_prefix(text + indexes[1], "and", 3));
```


Code after:
 * @param str The string being preprocessed
 * @param arg The bad char table
 * @returns void
 */
void init_bad_char(const std::string& str, std::vector<size_t>& arg) {
    arg.resize(APLHABET_SIZE, str.length());

    for (size_t i = 0; i < str.length(); i++) {
        arg[str[i]] = str.length() - i - 1;
    }
}

/**
 * @brief A function that initializes pattern
 *
 * @param str Text used for initialization
 * @param arg Initialized structure
 * @returns void
 */
void init_pattern(const std::string& str, pattern& arg) {
    arg.pat = str;
    init_bad_char(str, arg.bad_char);
    init_good_suffix(str, arg.good_suffix);
}
/**
 * @brief A function that implements Boyer-Moore's algorithm.
 *
 * @param str Text we are seatching in.
 * @param arg pattern structure containing the preprocessed pattern
 * @return Vector of indexes of the occurrences of pattern in text
 */
std::vector<size_t> search(const std::string& str, const pattern& arg) {
    size_t index_position = arg.pat.size() - 1;
    std::vector<size_t> index_storage;

    while (index_position < str.length()) {
        size_t index_string = index_position;
        int index_pattern = static_cast<int>(arg.pat.size()) - 1;

        while (index_pattern >= 0 &&
               str[index_string] == arg.pat[index_pattern]) {
            --index_pattern;
            --index_string;
        }

        if (index_pattern < 0) {
            index_storage.push_back(index_position - arg.pat.length() + 1);
            index_position += arg.good_suffix[0];
        } else {
            index_position += std::max(arg.bad_char[str[index_string]],
                                       arg.good_suffix[index_pattern + 1]);