Aho Corasick

Jump to bottom Edit New page

Matheus Santana edited this page Nov 14, 2013 · 4 revisions

Algoritmo BuildAFD
Entrada: P = p1 .. pm
Saída: AFD A t.q. L(A) = Σ*P

início
  delta <- tabela(m+1) x |Σ|
  delta[0, *] <- (0, .., 0)
  para j <- 1, .., m faça
    prev <- delta[j-1, ord(P[j])]
    delta[j-1, P[j]] <- j
    para c <- 1, .., |Σ| faça
      delta[j,c] <- delta[prev,c]
    fim-faça
  fim-faça
  retorna delta
fim

Texto: abaabab Padrão: aba

estado \ caractere    a     b
       0 (a)          0     0

estado \ caractere    a     b
       0 (a)          0     1
       1 (ab)         1     0

estado \ caractere    a     b
       0 (a)          0     1
       1 (ab)         0     1
       2 (aba)