Optimal prefix and suffix queries on texts

DOI10.1016/J.IPL.2008.05.027zbMATH Open1191.68205OpenAlexW1975060495WikidataQ61677924 ScholiaQ61677924MaRDI QIDQ975480FDOQ975480

Maxime Crochemore, Costas S. Iliopoulos, M. Sohel Rahman

Publication date: 9 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.05.027

Recommendations

• Optimal prefix and suffix queries on texts
• Position-restricted substring searching over small alphabets
• On position restricted substring searching in succinct space
• Position-Restricted Substring Searching
• Efficient indexes for the positional pattern matching problem and two related problems over small alphabets

zbMATH Keywords

algorithmsdata structurespattern matchingcombinatorial problems

Mathematics Subject Classification ID

Data structures (68P05) Nonnumerical algorithms (68W05)

Cites Work

• Algorithms on Strings, Trees and Sequences
• A greedy approximation algorithm for constructing shortest common superstrings
• Compressed representations of sequences and full-text indexes
• Dictionary matching and indexing with errors and don't cares
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Text Indexing and Dictionary Matching with One Error
• Jewels of Stringology
• A Space-Economical Suffix Tree Construction Algorithm
• Fast Pattern Matching in Strings
• Succinct data structures for flexible text retrieval systems
• An efficient algorithm for the all pairs suffix-prefix problem
• On-line construction of suffix trees
• Faster index for property matching
• Title not available (Why is that?)
• Title not available (Why is that?)
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• Position-Restricted Substring Searching
• Title not available (Why is that?)
• Finding Patterns with Variable Length Gaps or Don’t Cares
• Combinatorial algorithms for DNA sequence assembly
• Finding Patterns in Given Intervals
• Dynamic Entropy-Compressed Sequences and Full-Text Indexes
• Combinatorial Pattern Matching
• Parallel Suffix–Prefix-Matching Algorithm and Applications
• Combinatorial Pattern Matching
• Title not available (Why is that?)
• A linear-time algorithm for finding approximate shortest common superstrings
• Indexing Factors with Gaps
• Indexing Circular Patterns

Cited In (4)

• Substring range reporting
• Title not available (Why is that?)
• All-pairs suffix/prefix in optimal time using Aho-Corasick space
• Substring Range Reporting

This page was built for publication: Optimal prefix and suffix queries on texts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q975480)