/*
 *  Boyer-Moore Search
 *
 *  01.06.1998, implemented by Michael Neumann
 */

# include <algorithm>

int BoyerMooreSearch(char* text, char* muster, int tlen, int mlen)
{
    int i, j, skip[256];

    for(i=0; i<256; ++i)  skip[i]=mlen;
    for(i=0; i<mlen; ++i) skip[muster[i]]=mlen-1-i;

    for(i=j=mlen-1; j>0; --i, --j)
        while(text[i] != muster[j]) {
            i += max(mlen-j,skip[text[i]]);
            if(i >= tlen) return -1;
            j = mlen-1;
        }
    return i;
}