Forty Years of Text Indexing
From MaRDI portal
Publication:4928554
DOI10.1007/978-3-642-38905-4_1zbMath1381.68067MaRDI QIDQ4928554
No author found.
Publication date: 14 June 2013
Published in: Combinatorial Pattern Matching (Search for Journal in Brave)
Full work available at URL: https://hal-upec-upem.archives-ouvertes.fr/hal-01246128/file/ACFGM2013.pdf
pattern matching; suffix array; suffix tree; string searching; factor automaton; directed acyclic word graph; wavelet tree; FM-index; suffix automaton; DAWG; bi-tree
68Q45: Formal languages and automata
68P05: Data structures
68U15: Computing methodologies for text processing; mathematical typography
68W32: Algorithms on strings
Related Items
Longest common substring made fully dynamic, Dynamic and internal longest common substring, A suffix tree or not a suffix tree?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Automata and forbidden words
- Using minimal absent words to build phylogeny
- Let sleeping files lie: Pattern matching in Z-compressed files.
- The smallest automaton recognizing the subwords of a text
- Time optimal left to right construction of position trees
- Parallel construction of a suffix tree with applications
- Optimal off-line detection of repetitions in a string
- Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Transducers and repetitions
- Detection of periodicities and string-matching in real time
- On-line construction of suffix trees
- Data structures and algorithms for the string statistics problem
- On-line construction of two-dimensional suffix trees in \(O(n^{2} \log n)\) time
- The myriad virtues of wavelet trees
- Constructing suffix arrays in linear time
- Space efficient linear time construction of suffix arrays
- Suffix Arrays: A New Method for On-Line String Searches
- Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
- Fast Algorithms for Finding Nearest Common Ancestors
- Compressing and indexing labeled trees, with applications
- Indexing compressed text
- Optimal parallel algorithms for string matching
- Efficient On-Line Construction and Correction of Position Trees
- Linear Algorithm for Data Compression via String Matching
- Data compression via textual substitution
- A Space-Economical Suffix Tree Construction Algorithm
- On the Complexity of Finite Sequences
- Algorithms on Strings, Trees and Sequences
- Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance
- Minimal forbidden words and symbolic dynamics
- Complete inverted files for efficient text retrieval and analysis
- The macro model for data compression (Extended Abstract)
- Algorithms on Strings
