Automate des occurrences

De AgregmathKL
Révision de 26 février 2015 à 21:12 par Mathias Millet (discuter | contributions)

(diff) ← Version précédente | Voir la version courante (diff) | Version suivante → (diff)
Aller à : navigation, rechercher

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

Tex Automate des occurrences.pdf

Recasements

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).