Reverse Engineering Prefix Tables

Abstract : The Prefix table of a string reports for each position the maximal length of its prefixes starting here. The Prefix table and its dual Suffix table are basic tools used in the design of the most efficient string-matching and pattern extraction algorithms. These tables can be computed in linear time independently of the alphabet size. We give an algorithmic characterisation of a Prefix table (it can be adapted to a Suffix table). Namely, the algorithm tests if an integer table of size n is the Prefix table of some word and, if successful, it constructs the lexicographically smallest string having it as a Prefix table. We show that the alphabet of the string can be bounded to log2 n letters. The overall algorithm runs in O(n) time.
Type de document :
Communication dans un congrès
Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.289-300, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00359304
Contributeur : Publications Loria <>
Soumis le : vendredi 6 février 2009 - 15:15:08
Dernière modification le : mardi 5 juin 2018 - 10:14:41
Document(s) archivé(s) le : mardi 8 juin 2010 - 19:13:06

Fichier

24-clement.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00359304, version 1

Citation

Julien Clément, Maxime Crochemore, Giuseppina Rindone. Reverse Engineering Prefix Tables. Susanne Albers and Jean-Yves Marion. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. IBFI Schloss Dagstuhl, pp.289-300, 2009, Proceedings of the 26th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00359304〉

Partager

Métriques

Consultations de la notice

463

Téléchargements de fichiers

207