Skip to Main content Skip to Navigation
Journal articles

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 Makinen and Navarro [V. Makinen, G. Navarro, Position-restricted substring searching, in: J.R. Correa, A. Hevia, M.A. Kiwi (Eds.), LATIN, in: Lecture Notes in Computer Science, vol. 3887, Springer, 2006, pp. 703-714]. 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 Makinen and Navarro, if applied to our problem, gives sub-optimal query time and the corresponding data structure also requires more time and space.
Document type :
Journal articles
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00619725
Contributor : Maxime Crochemore <>
Submitted on : Thursday, February 14, 2013 - 8:43:54 AM
Last modification on : Wednesday, February 26, 2020 - 7:06:05 PM
Long-term archiving on: : Wednesday, May 15, 2013 - 2:25:08 AM

File

CIROptPreQueries.pdf
Files produced by the author(s)

Identifiers

Citation

Maxime Crochemore, Costas S. Iliopoulos, Mohammad Sohel Rahman. Optimal Prefix and Suffix Queries on Texts. Information Processing Letters, Elsevier, 2008, 108 (5), pp.320-325. ⟨10.1016/j.ipl.2008.05.027⟩. ⟨hal-00619725⟩

Share

Metrics

Record views

411

Files downloads

400