Boyer Moore Algorithm

Boyer Moore Algorithm == Bad character Algorithm
worst case O(nm + s)
average case O(n/m)



[-] Collapse

//KMP string match

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int L[125];//Last Occurrence
void pre_Process(string str){
    for (int i = 0; i < 125; i++)
        L[i] = -1; //나중에 s.size()만큼 이동하기 위해서
    for (int i = 0; i < str.size(); i++)
        L[str[i]] = i;
}
int Boyer_Moore(string l, string s){
    int i = s.size() - 1;
    int j = s.size() - 1;
    while (i < l.size()){
        if (l[i] == s[j]){
            if (j == 0) return i;
            else i--, j--;
        }
        else{ //bad character!
            i = i + s.size() - min(j, 1 + L[l[i]]);
            j = s.size() - 1;
        }

    }
    return -1;// find fail
}
int main(){