EXACT STRING MATCHING ALGORITHMS

[Lennon de Almeida Machado <lennonx@hotmail.com>]

Prof Yoshi,

Nosso colega Michel ja havia encontrado um dos algoritmos de pattern
matching com tempo de execucao proporcional a O(n+m), segue aqui um site
interessante, com exemplos "animados" do procedimento utilizado pelo
algoritmo.

http://www.dir.univ-rouen.fr/~charras/string/

Lennon Machado
23/3/99 8h10min

Title: EXACT STRING MATCHING ALGORITHMS

 Next: Contents

---

EXACT STRING MATCHING ALGORITHMS

Christian Charras - Thierry Lecroq
Laboratoire d'Informatique de Rouen
Université de Rouen
Faculté des Sciences et des Techniques
76821 Mont-Saint-Aignan Cedex
FRANCE

---

• Contents
• Introduction
• Brute force algorithm
• Research with an automaton
• Karp-Rabin algorithm
• Shift Or algorithm
• Morris-Pratt algorithm
• Knuth-Morris-Pratt algorithm
• Simon algorithm
• Colussi algorithm
• Galil-Giancarlo algorithm
• Apostolico-Crochemore algorithm
• Not So Naive algorithm
• Boyer-Moore algorithm
• Turbo-BM algorithm
• Apostolico-Giancarlo algorithm
• Reverse Colussi algorithm
• Horspool algorithm
• Quick Search algorithm
• Zhu-Takaoka algorithm
• Smith algorithm
• Raita algorithm
• Reverse Factor algorithm
• Turbo Reverse Factor algorithm
• Galil-Seiferas algorithm
• Two Way algorithm
• String Matching on Ordered Alphabets
• Optimal Mismatch algorithm
• Maximal Shift algorithm
• Skip Search algorithm
• KmpSkip Search algorithm
• Alpha Skip Search algorithm
• ps file

---

LIR & DIR Tue Jan 14 15:03:31 MET 1997