Un automate qui cherche un motif

L'idée, et c'est la seule. L'état retenu est la longueur du plus long préfixe du motif qui soit un suffixe de ce qu'on a lu. Cette quantité est bornée par la longueur du motif, donc les états sont $0,1,2,3$, et l'on pose

$$\delta (q,x)=\text{longueur du plus long preˊfixe de aba suffixe de }(\text{aba}[\mathrm{0..}q-1]x).$$

Le calcul donne, avec $3$ absorbant :

Noter $\delta (1,a)=1$ et non $2$ : après aa, le plus long préfixe de aba qui soit un suffixe est a, de longueur $1$. C'est là que le recouvrement se joue.

Pour compter, on rend l'état $3$ non absorbant en lui appliquant la même règle : après aba, le plus long préfixe de aba qui soit un suffixe de abaa est a, et de abab est ab. Donc $\delta (3,a)=1$ et $\delta (3,b)=2$. On incrémente un compteur chaque fois qu'on entre en $3$.

Mesures. La table absorbante a été comparée au prédicat « contient aba » sur les $8191$ mots de longueur au plus $12$ : accord complet. La variante comptante trouve $3$ occurrences dans abababa, $2$ dans ababab, $1$ dans aabab, $0$ dans aaa — chaque fois le compte exact avec recouvrements.

Le coût. La recherche est en $\Theta (n)$, une lecture par caractère, sans jamais revenir en arrière — ce qu'aucun des deux algorithmes du chapitre chap:textes ne garantit : la version simplifiée de Boyer-Moore reste en $O(nm)$ au pire, et Rabin-Karp n'est linéaire qu'en moyenne. Le prix est la table, $\Theta (|m|\cdot |\Sigma |)$ en place.