Linear-size suffix tries

DOI10.1016/J.TCS.2016.04.002MaRDI QIDQ294967zbMATH OpenOpenAlexWikidataFDO

Authors Maxime Crochemore, C. Epifanio, Roberto Grossi, Filippo Mignosi

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 matchingfactor and suffix automatasuffix treetext indexing

Mathematics Subject Classification ID

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

Recommendations

• Space efficient suffix trees
• Compressed suffix trees with full functionality
• Suffix trees on words

Cites work

• scientific article; zbMATH DE number 1962793 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 1786457 (Why is no real title available?)
• scientific article; zbMATH DE number 1445802 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• Algorithms on Strings, Trees and Sequences
• An efficient algorithm for the all pairs suffix-prefix problem
• Average sizes of suffix trees and DAWGs
• Combinatorial Pattern Matching
• Fully compressed suffix trees
• Near real-time suffix tree construction via the fringe marked ancestor problem
• New algorithms for position heaps
• On-line construction of compact directed acyclic word graphs
• On-line construction of position heaps
• Position heaps: a simple and dynamic text indexing data structure
• Reducing space for index implementation.
• The smallest automaton recognizing the subwords of a text

Cited in

(10)

• Online algorithms for constructing linear-size suffix trie
• Fast label extraction in the CDAWG
• On minimal and maximal suffixes of a substring
• Computing minimal and maximal suffixes of a substring
• Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays
• Linear time online algorithms for constructing linear-size suffix trie
• Alphabet-dependent string searching with wexponential search trees
• Linear-size suffix tries and linear-size CDAWGs simplified and improved
• Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets
• Linear-size CDAWG: new repetition-aware indexing and grammar compression

Describes a project that uses

Uses Software

• PATRICIA

This page was built for publication: Linear-size suffix tries

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