Linear-size suffix tries

DOI10.1016/j.tcs.2016.04.002zbMath1344.68057OpenAlexW2317728333WikidataQ61677829 ScholiaQ61677829MaRDI QIDQ294967

Chiara Epifanio, Filippo Mignosi, Maxime Crochemore, Roberto Grossi

Publication date: 16 June 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.04.002

zbMATH Keywords

pattern matchingsuffix treefactor and suffix automatatext indexing

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Data structures (68P05) Information storage and retrieval of data (68P20) Algorithms on strings (68W32)

Related Items

Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets ⋮ Fast Label Extraction in the CDAWG ⋮ Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression ⋮ Online algorithms for constructing linear-size suffix trie

Uses Software

• PATRICIA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On-line construction of position heaps
• Position heaps: a simple and dynamic text indexing data structure
• The smallest automaton recognizing the subwords of a text
• An efficient algorithm for the all pairs suffix-prefix problem
• On-line construction of compact directed acyclic word graphs
• Average sizes of suffix trees and DAWGs
• Reducing space for index implementation.
• Near real-time suffix tree construction via the fringe marked ancestor problem
• Fully compressed suffix trees
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• New Algorithms for Position Heaps
• Combinatorial Pattern Matching