Szukanie wzorca w tekscie metodą Boyera-Moorea

Jest to chyba najszybszy algorytm na wyszukiwanie wzorca w texcie (złożoność teoretyczna to O(N/M) !!!) Jest on niesamowicie szybki przy dużych ciągach znakowych o sporym alfabecie.

<-- i ---------------------------------------------------->
a v e , C a e s a r , m o r i t u r i t e s o l u t a n t
s o l u t
             s o l u t
                       s o l u t
                              s o l u t
                                        s o l u t
                                                   s o l u t
                                                        s o l u t
Jak widać z przykładu gdy algorytm sprawdzając ostatnią litere poszukiwanego wzorca do ciagu tekstu uzna za nie równą przeskakuje o całą długość wzorca, sprawdza jednak czy nie występują jakieś znaki które znajdują się we wzorcu, jeśli tak to nie przesuwa się o całą długość wzorca a tylko o taką długość aby te same znaki we wzorcu i tekscie pokryły się.
Metoda wykorzystuje zbadaną część wzorca do wyznaczenia optymalnego przesunięcia wzorca względem badanego fragmentu tekstu. Do tego
celu na wstępie generowana jest tablica optymalnych przesunięć shift. Algorytm wykonywany jest do momentu, aż cały fragment teksu będzie zgodny ze wzorcem, bądź osiągniemy koniec tekstu.
a teraz kod:

const K = 53; // litery(26+26) i spacja (1)
int shift[K];

int indeks(char c)
{ switch(c) {
     case 32: return 0; // spacja
     default: if(islower(c)) return c-'a'+1;
                 else return c-'A'+27;
     }
}

void InitShift(char *w)
{
   int i;
   for(i=0; i < K; i++) shift[i]=M;
      for(i=0; i < M; i++) shift[indeks(w[i])]=M-i-1;
}

int BM(char *t, char *w)
{
   int i,j,N=strlen(t),x;
   for(i=M-1,j=M-1; j > 0; i--,j--)
   while( t[i]!=w[j] )
   { x=shift[indeks(t[i])];
      if(M-j > x) i+=M-j; else i+=x;
        if(i >= N) return -1;
        j=M-1;
   }
   return i;
}