请教Wu_manber算法
请教Wu_manber算法
请尽量给出具体的实现代码 谢谢!
[解决办法]
%/* Funcao : Wu_Manber
% Objetivos : verifica se um padrao ocorre ou nao numa sequencia, com um
% numero de erros menor ou igual a k
% Parametros: o padrao, a sequencia e o numero de erros
% Saida : verdadeiro se o padrao ocorre na sequencia ou falso, caso
% contrario */
%long Wu_Manber(char *p, char *t, long k) {
% long i,
% j,
% m, /* tamanho do padrao */
% n, /* tamanho da sequencia */
% matchfound, /* diz se um casamento foi encontrado */
% R0[MAX_NUMBER_OF_ERRORS], /* mascaras de estado anterior */
% R1[MAX_NUMBER_OF_ERRORS]; /* mascaras de estado atual */
% char newt[MAX_MODIFIED_LINE_SIZE]; /* sequencia entre espacos */
%
% strcpy(newt, " ");
% strcat(newt, t);
% strcat(newt, " ");
% n = strlen(newt);
% m = strlen(p);
% matchfound = FALSE;
% for (i = 0; i <= k; i++) { /* inicializa mascaras de estado */
% R1[i] = Start[i];
% R0[i] = Start[i];
% }
% for (i = 0; i < n; i++) { /* executa o algoritmo */
% R1[0] = ((R0[0] > > 1) & S[newt[i]]) | (Start[0] & R0[0]);
% for (j = 1; j <= k; j++) {
% R1[j] = ((R0[j] > > 1) & S[newt[i]]) |
% ((R0[j-1] | ((R1[j-1] | R0[j-1]) > > 1)) & M) | (Start[0] & R0[j]);
% }
% for (j = 0; j <= k; j++) { /* atribui estado atual no anterior */
% R0[j] = R1[j];
% if (R1[j] & 1) { /* se bit menos significativo estiver ativo, entao
% tem-se um casamento na linha atual do texto */
% matchfound = TRUE;
% }
% }
% }
% return matchfound;
%}
