Optimal Prefix and Suffix Queries on Texts

Abstract : In this paper, we study a restricted version of the position restricted pattern matching problem introduced and studied by Mäkinen and Navarro [Position-Restricted Substring Searching, LATIN 2006]. In the problem handled in this paper, we are interested in those occurrences of the pattern that lies in a suffix or in a prefix of the given text. We achieve optimal query time for our problem against a data structure which is an extension of the classic suffix tree data structure. The time and space complexity of the data structure is dominated by that of the suffix tree. Notably, the (best) algorithm by Mäkinen and Navarro, if applied to our problem, gives sub-optimal query time and the corresponding data structure also requires more time and space.
Type de document :
Communication dans un congrès
Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.47-56, 2007, DMTCS Proceedings
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01184789
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 16:59:51
Dernière modification le : jeudi 11 janvier 2018 - 06:20:22
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:17:28

Fichier

dmAH0104.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184789, version 1

Collections

Citation

Maxime Crochemore, Costas S. Iliopoulos, M. Sohel Rahman. Optimal Prefix and Suffix Queries on Texts. Jacquet, Philippe. 2007 Conference on Analysis of Algorithms, AofA 07, 2007, Juan les Pins, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), pp.47-56, 2007, DMTCS Proceedings. 〈hal-01184789〉

Partager

Métriques

Consultations de la notice

141

Téléchargements de fichiers

53