Quick actions

cmd+k|ctrl+k

Navigation

Languages

Boyer-Moore`s algorithm

Snippet info

Language

Cpp

Visibility

public

Author

n-piatygorskiy

Created

2021-05-15T20:30:06.496554Z

Updated

2021-05-15T20:30:06.496554Z

#include <iostream>
#include <cstring>
#include <cstring>
#define TableSize 256

using namespace std;

void fillShift(char* pattern, int* table) {
    int len = strlen(pattern);
    table[pattern[len - 1]] = len;
    for (int i = len - 2; i >= 0; i--) {
        table[pattern[i]] = len - i - 1;
    }
}

int strFind(char* pattern, char* target) {
    int tarlen = strlen(target);
    int patlen = strlen(pattern);
    int patpos = patlen - 1;
    int tarpos = patpos;
    int table[TableSize];
    fill(table, table + TableSize, patlen);
    fillShift(pattern, table);
    while (tarpos < tarlen) {
        int temp = tarpos;
        while (target[tarpos] == pattern[patpos] && patpos >= 0) {
            tarpos--;
            patpos--;
        }
        if (patpos < 0) return tarpos + 1;                          //Full matching of pattern
        else {
            patpos = patlen - 1;
            tarpos = temp + table[target[tarpos]];
        }
    }
    return -1;          //didnt find anything
}

char target[] = "This is string we want to find first occurrence";
char pat[] = "find";

int main() {
    cout << strFind(pat, target);
    return 0;
}
INFO