O Algoritmo Shift-end

SHIFT END EXATO(MÁSCARA)

/* Procedimento que realiza o pre-processamento do padrao, construindo

* as mascaras para cada caractere do alfabeto.

*/

void shiftAndPreprocess() {

int j, k=1;

char a;

for (j=0; j<m; j++){ // anel do pre-processamento

a=p[j]; // recupera o j-esimo caractere do padrão

ch[a]|=k; // atribui 1 ao j-esimo bit do j-esimo

// caractere do padrao

lastbit=k;

k<<=1;

}

SHIFT END EXATO

/* Procedimento que realiza a busca exata de um padrao na

* colecao de textos.

*/

void shiftAndSearch() {

int i, r=0 // registrador que representa o automato

for (i=0; i < 256; i++) ch[i]= 0; // Incializa o alfabeto com mascara

// de valor zero (0).

shiftAndPreprocess(); // Realiza o pre-processamento do padrao

for (i=0; i<n; i++){

r=((r<<1) | 1) & ch[t[i]]; // Deslocamento para a esquerda (uma vez

// que o registrador esta invertido) e

// execucao de um "and" com a mascara do

// caractere corrente.

if ((r & lastbit)!=0)

output(i-m+1); // Testa se o ultimo bit do

// registrador foi alcancado,

// que define o casamento

}

}