Facteur, sous-mot, préfixe : compter

Pour $u=\text{abab}$, de longueur $4$ :

• préfixes non vides : $\text{a},\text{ab},\text{aba},\text{abab}$ — il y en a toujours exactement $n=4$, un par longueur ;
• suffixes non vides : $\text{b},\text{ab},\text{bab},\text{abab}$ — également $4$ ;
• facteurs distincts : $\text{a},\text{b},\text{ab},\text{ba},\text{aba},\text{bab},\text{abab}$ — 7, alors que la borne $n(n+1)/2=10$ compte les positions ; trois coïncidences ($\text{a}$, $\text{b}$ et $\text{ab}$ apparaissent deux fois) les font tomber à $7$ ;
• sous-mots distincts : $\text{a},\text{b},\text{aa},\text{ab},\text{ba},\text{bb},\text{aab},\text{aba},\text{abb},\text{bab},\text{abab}$ — 11, contre une borne $2^4-1=15$.

Pour $u=\text{aaaa}$, les deux comptes s'effondrent à $4$ : les seuls facteurs sont $\text{a},\text{aa},\text{aaa},\text{aaaa}$, et ce sont aussi les seuls sous-mots. Un mot sur un alphabet à une lettre n'a qu'une information : sa longueur.

Ce que l'exercice fixe. Les deux notions ne se recoupent que par accident. $\text{abb}$ est un sous-mot de $\text{abab}$ — on garde $u_1$, $u_2$, $u_4$ — mais n'en est pas un facteur, puisqu'il n'y a nulle part deux $\text{b}$ consécutifs. C'est exactement la distinction annoncée par le chapitre, et elle décide de tout ce qui suit : la recherche de motif porte sur les facteurs (Boyer-Moore, Rabin-Karp), la plus longue sous-suite commune du chapitre chap:dynamique porte sur les sous-mots. Les algorithmes n'ont rien à voir, et les complexités non plus : $O(n)$ en moyenne d'un côté, $\Theta (nm)$ de l'autre.