Facteur, sous-mot, préfixe : compter

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 18 — Algorithmique des textes

Énoncé

Pour le mot $u = abab$ , dénombrer les préfixes non vides, les suffixes non vides, les facteurs distincts et les sous-mots distincts. Comparer aux bornes $n$ , $n (n + 1) /2$ et $2^{n} - 1$ . Que donne $u = aaaa$ ?

Corrigé

Pour $u = abab$ , de longueur $4$ :

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

Pour $u = aaaa$ , les deux comptes s'effondrent à $4$ : les seuls facteurs sont $a, aa, aaa, 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. $abb$ est un sous-mot de $abab$ — on garde $u_{1}$ , $u_{2}$ , $u_{4}$ — mais n'en est pas un facteur, puisqu'il n'y a nulle part deux $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é, $Θ (nm)$ de l'autre.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.