[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico] [Índice de assunto]

RE: EXACT STRING MATCHING ALGORITHMS



Lennon de Almeida Machado writes:
 > Prof Yoshi,
 > 
 > Nosso colega Michel ja havia encontrado um dos algoritmos de pattern
 > matching com tempo de execucao proporcional a O(n+m), 

Dar aula para voces vai me custar caro, pelo que estou vendo...  Acho
fantastico!  O Michel poderia dar mais detalhes?

 >                                                       segue aqui um site
 > interessante, com exemplos "animados" do procedimento utilizado pelo
 > algoritmo.

Muito bacana; nao conhecia.  Uma curiosidade, o algoritmo de Simon que aparece
neste site foi bolado pelo prof. Imre Simon, do nosso departamento aqui do
IME. 

O algoritmo padrao de tempo O(n+m) é o algoritmo de Knuth, Morris e Pratt.  

Abracos a todos!  Yoshi

 > http://www.dir.univ-rouen.fr/~charras/string/
 > 
 > Lennon Machado
 > 23/3/99 8h10min