Back to Search
Start Over
Optimal Prefix and Suffix Queries on Texts
- Source :
- Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AH,..., Iss Proceedings (2007)
- Publication Year :
- 2007
- Publisher :
- Discrete Mathematics & Theoretical Computer Science, 2007.
-
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.
- Subjects :
- algorithms
pattern matching
index
data structures
suffix trees
[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
[info.info-cg] computer science [cs]/computational geometry [cs.cg]
Mathematics
QA1-939
Subjects
Details
- Language :
- English
- ISSN :
- 13658050
- Volume :
- DMTCS Proceedings vol. AH,...
- Issue :
- Proceedings
- Database :
- Directory of Open Access Journals
- Journal :
- Discrete Mathematics & Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.99ff4b13354346168c093ec53d440723
- Document Type :
- article
- Full Text :
- https://doi.org/10.46298/dmtcs.3541