Fetching the paper…
Reading the bibliography…
The linear-size suffix tries (LSTries) [Crochemore et al., TCS 2016] are a version of suffix trees in which the edge labels are single characters, yet are able to perform pattern matching queries in optimal time.
Linear pattern matching algorithms
P. Weiner · 1973
Earlier work this paper cites.
A universal algorithm for sequential data compression
J. Ziv and A. Lempel · 1977
Earlier work this paper cites.
The smallest automation recognizing the subwords of a text
A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, and J. Seiferas · 1985
Earlier work this paper cites.
Complete inverted files for efficient text retrieval and analysis
A. Blumer, J. Blumer, D. Haussler, R. McConnell, and A. Ehrenfeucht · 1987
Earlier work this paper cites.
Finding level-ancestors in trees
O. Berkman and U. Vishkin · 1994
Earlier work this paper cites.
On-line construction of suffix trees
E. Ukkonen · 1995
Earlier work this paper cites.
The LCA problem revisited
M. A. Bender and M. Farach-Colton · 2000
Earlier work this paper cites.
Application of Lempel-Ziv factorization to the approximation of grammar-based compression
W. Rytter · 2003
Earlier work this paper cites.
Discovering instances of poetic allusion from anthologies of classical Japanese poems
M. Takeda, T. Fukuda, I. Nanri, M. Yamasaki, and K. Tamari · 2003
Earlier work this paper cites.
The level ancestor problem simplified
M. A. Bender and M. Farach-Colton · 2004
Cited alongside, same era.
The smallest grammar problem
M. Charikar, E. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, and A. Shelat · 2005
Cited alongside, same era.
Dynamic LCA queries on trees
R. Cole and R. Hariharan · 2005
Cited alongside, same era.
Real-time traversal in grammar-based compressed files
L. Gasieniec, R. M. Kolpakov, I. Potapov, and P. Sant · 2005
Cited alongside, same era.
On-line construction of compact directed acyclic word graphs
S. Inenaga, H. Hoshino, A. Shinohara, M. Takeda, S. Arikawa, G. Mauri, and G. Pavesi · 2005
Cited alongside, same era.
The structure of subword graphs and suffix trees of Fibonacci words
W. Rytter · 2006
Cited alongside, same era.
Personal communication, 2017
J. Kärkkäinen · 2017
Later among the works it cites.
Efficient computation of substring equivalence classes with suffix arrays
K. Narisawa, H. Hiratsuka, S. Inenaga, H. Bannai, and M. Takeda · 2017
Later among the works it cites.
Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression
T. Takagi, K. Goto, Y. Fujishige, S. Inenaga, and H. Arimura · 2017
Later among the works it cites.
At the roots of dictionary compression: string attractors
D. Kempa and N. Prezza · 2018
Later among the works it cites.
Online Algorithms for Constructing Linear-size Suffix Trie
D. Hendrian, T. Takagi, and S. Inenaga · 2019
Later among the works it cites.
Indexing highly repetitive string collections, part I: repetitiveness measures
G. Navarro · 2022
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
On the structure of compacted subword graphs of Thue-Morse words and their applications
J. Radoszewski and W. Rytter · 2012
Cited alongside, same era.
Linear-size suffix tries
M. Crochemore, C. Epifanio, R. Grossi, and F. Mignosi · 2016
Cited alongside, same era.
Fast label extraction in the CDAWG
D. Belazzougui and F. Cunial · 2017
Cited alongside, same era.
Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets
Y. Fujishige, Y. Tsujimaru, S. Inenaga, H. Bannai, and M. Takeda · 2023
Later among the works it cites.
Linear time online algorithms for constructing linear-size suffix trie
D. Hendrian, T. Takagi, S. Inenaga, K. Goto, and M. Funakoshi · 2023
Later among the works it cites.