#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXCHAR 256

int BMH(char *T, char *P)
{
    int i, j, k;
    int n = strlen(T);
    int m = strlen(P);
    int d[MAXCHAR];

    //pré-processamento
    for (j=0; j<MAXCHAR; j++) {
        d[j] = m;
    }
    for (j=1; j<m; j++) {
        d[P[j-1]] = m-j;
    }
    i = m;
    //busca
    while (i <= n) {
        k = i;
        j = m;
        while (T[k-1] == P[j-1] && j > 0) {
            k--;
            j--;
        }
        if (j == 0)
            return k+1;
        i += d[T[i - 1]];
    }
    return -1;
}

int main()
{
    char texto[] = "aabcacbacbacac";
	char padrao[] = "cacbac";

    int ocorr;

    ocorr = BMH(texto, padrao);
    printf("Casamento na posição: %d \n", ocorr);
    return 0;
}