String Matching Algorithms and Automata

I. Simon

IBP-Litp 1994/47: Rapport de Recherche Litp / Litp research reports
10 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: String Matching Algorithms and Automata

Résumé : Dans cet article nous étudions la structure des automates finis reconnaissant les ensembles de la forme A*p , où p est un mot quelconque, et nous utilisons les réultats obtenus pour améliorer l'algorithme de recherche de motif de Knuth - Morris - Pratt. Nous déterminons aussi le nombre moyen de flèches non triviales des automates ci-dessus.

Abstract : In this paper we study the structure of finite automata recognizing sets of the form A* p , for some word p , and use the results obtained to improve the Knuth-Morris - Pratt string searching algorithm. We also determine the average number of nontrivial edges of the above automata.

Publications internes Litp 1994 / Litp research reports 1994