Oracle des facteurs: une nouvelle structure pour la recherche de mots

Nous définissons un nouvel automate sur un mot $p=p_1p_2 \cdots p_m$, suite de lettres prises dans un alphabet $\Sigma$, que nous appelons oracle des facteurs. Cet automate est acyclique, reconnaît au moins les facteurs de $p$, a $m+1$ états, est linéaire en nombre de transitions. Nous donnons un algorithme de construction séquentielle de l'oracle des facteurs. Les liens étroits de cette structure avec l'automate des suffixes nous permettent d'introduire une deuxième structure, l'oracle des suffixes. Ces deux structures sont utilisées dans des algorithmes de recherche de mots, que nous conjecturons optimaux en moyenne, au vu des résultats expérimentaux. Ces algorithmes sont aussi efficaces que ceux qui existent déjà, tout en utilisant moins de place mémoire et en étant beaucoup plus simples à implémenter. Nous étendons ensuite cette structure à un ensemble de mots, et nous l'utilisons dans de nouveaux algorithmes de recherche d'ensembles de mots dans des textes. Ces algorithmes sont les plus efficaces en pratique.