Nombre de tables de préfixes et des bords

La table des préfixes d’un mot w contient pour chaque position i la longueur du sous mot le plus long de w qui commence en i et correspond à un préfixe de w. Cette table contient les mêmes informations que la table des bords de w , qui indique pour chaque position i la longueur maximale des préfixes de w finissant à cette position. En effet deux mots ont la même table des bords si et seulement s’ils ont la même table des préfixes.

Les deux tables sont utiles dans plusieurs algorithmes sur les mots. Elles sont utilisées pour concevoir des algorithmes efficaces de string-matching et sont essentielles pour ce type d’applications. On remarque que pour quelques algorithmes du texte (comme l’algorithme de pattern-matching de Knuth-Morris- Pratt), on ne considère pas le mot lui-même, mais plutôt sa structure signifiant que deux mots avec la même table des préfixes ou des bords sont traités de la même façon. L’étude de ces tables est devenue fondamentale et c’est un sujet récent qui intéresse plusieurs auteurs.

Dans cet exposé on considère le problème d’énumérer les tables de préfixes et de bords d’une longueur fixée. Dans ce but, nous définissons la classe combinatoire des p-listes, où une p-liste est une séquence finie d’entiers non négatifs. Nous définissons de manière constructive une injection de l’ensemble des tables de préfixes à l’ensemble des p-listes qui sont plus faciles à compter. Nous déduisons alors une nouvelle borne supérieure et une nouvelle borne inférieure sur le nombre de tables de préfixes pour les mots de longueur n ou, de façon équivalente, sur le nombre des tables de bords de longueur n.