Résumé
Les chevauchements entre les mots sont essentiels dans de nombreux domaines de l'informatique, tels que la conception de code, l'algorithmique du texte et la bio-informatique. Un mot auto-chevauchant est caractérisé par ses périodes et ses bords. Une période d'un mot $u$ est la position de départ d'un suffixe de $u$ qui est également un préfixe $u$, et un tel suffixe est appelé un bord de $u$. Chaque mot de longueur, disons $n>0$, possède un ensemble de périodes, mais toutes les combinaisons d'entiers ne sont pas des ensembles de périodes. Le calcul de l'ensemble des périodes d'un mot $u$ prend un temps linéaire par rapport à la longueur de $u$. Nous abordons la question du calcul de l'ensemble, noté $\Gamma_n$, de tous les ensembles de périodes de mots de longueur $n$. Bien que les ensembles de périodes aient été caractérisés, il n'existe aucune formule pour calculer la cardinalité de $\Gamma_n$ (qui est exponentielle en $n$), et l'algorithme de programmation dynamique connu pour énumérer $\Gamma_n$ souffre de sa complexité en espace. Nous présentons une approche incrémentale pour calculer $\Gamma_n$ à partir de $\Gamma_{n-1}$, approche qui réduit la complexité en espace, puis un algorithme de certification constructif utile à des fins de vérification. L'approche incrémentale définit une relation parentale entre les ensembles dans $\Gamma_{n-1}$ et $\Gamma_n$, ce qui permet d'étudier la dynamique des ensembles de périodes et leurs propriétés statistiques intrigantes. De plus, l'ensemble de périodes d'un mot $u$ est la clé pour calculer la probabilité d'absence de $u$ dans des textes aléatoires, ce qui souligne son importance pratique.