Boyer-Moore`s algorithm
123456789101112131415161718192021222324252627282930313233343536373839404142434445
#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;
}
Cpp
INFO