Ukkonen

A ideia é construir um AFD para simular a execução do algoritmo Sellers.

Dado padrão fixo P = p1, ..., pm e r t.q. r >= 0, o AFD Ap,r simula a passagem de uma coluna da matriz de P.D. para a seguinte, respondendo a caracteres no texto T.

O autômato Ap,r é definido pela 5-upla <Q,Σ,δ,q0, F> onde

• Q = { S = (s0,...sm)^T | s é possível vetor coluna da matriz de P.D. D(P,T) com P fixo e T qualquer }
• q0 = (0,1,2,...,m)^T
• δ : Q x Σ -> Q

(s,a) |-> S' = (0,s',...,s'm)
tal que si = min { si-1 + φ(P[i], a), si+1, s'i-1 + 1 }

• F = { S = (s0,...,sm)^T | Sm <= r }