Automate des occurrences
De AgregmathKL
Ce développement présente une implémentation de l'algorithme de Morris-Pratt par un automate fini : L'automate des occurrences.
Remarques
- Il faut pouvoir expliciter l'algorithme qui calcule la fonction de transition dans l'automate (algorithme de calcul des bords maximaux [Beauquier] modifié)
- Il y a une démonstration par récurrence [Cormen, p.886] qui évite l'introduction de morphisme d'automate.
Le développement
Recasements
- 907 -- Algorithmique du texte : exemples et applications.
- 908 -- Automates Finis, exemples et applications
Références
- Beauquier p.350 à 354
(Il est à noter que la preuve donnée du théorème (Proposition 1.9) est incomplète).