A linear time lower bound on McCreight and general updating algorithms for suffix trees

DOI10.1007/s00453-003-1034-5zbMath1069.68548OpenAlexW2041306856WikidataQ58001539 ScholiaQ58001539MaRDI QIDQ1879368

Paulo D. Conejo, Mauricio Ayala-Rincón

Publication date: 22 September 2004

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-003-1034-5

zbMATH Keywords

Linear-time algorithmSuffix treeSuffix trie

Mathematics Subject Classification ID

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

Related Items

A linear time lower bound on McCreight and general updating algorithms for suffix trees

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal algorithm for computing the repetitions in a word
• Optimal off-line detection of repetitions in a string
• From Ukkonen to McCreight and Weiner: A unifying view of linear-time suffix tree construction
• Matching a set of strings with variable length don't cares
• A linear time lower bound on McCreight and general updating algorithms for suffix trees
• On-line construction of suffix trees
• Suffix Arrays: A New Method for On-Line String Searches
• A Space-Economical Suffix Tree Construction Algorithm