Computing runs on a trie
From MaRDI portal
Publication:5088914
DOI10.4230/LIPIcs.CPM.2019.23OpenAlexW2955399512MaRDI QIDQ5088914
Shunsuke Inenaga, Masayuki Takeda, Ryo Sugahara, Hideo Bannai, Yuto Nakashima
Publication date: 18 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.CPM.2019.23
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Longest common extensions in trees
- Extracting powers and periods in a word from its runs structure
- The level ancestor problem simplified
- Computing runs on a general alphabet
- A linear-time algorithm for a special case of disjoint set union
- The suffix tree of a tree and minimizing sequential transducers
- An on-line string superprimitivity test
- String powers in trees
- The maximal number of cubic runs in a word
- Near-optimal computation of runs over general alphabet via non-crossing LCE queries
- Squares, cubes, and time-space efficient string searching
- Efficient counting of square substrings in a tree
- The Maximum Number of Squares in a Tree
- Constructing Efficient Dictionaries in Close to Sorting Time
- Range Predecessor and Lempel-Ziv Parsing
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
- The “Runs” Theorem
- Faster Longest Common Extension Queries in Strings over General Alphabets
