Efficiently computing runs on a trie

DOI10.1016/j.tcs.2021.07.011OpenAlexW3184027729MaRDI QIDQ820550

Ryo Sugahara, Masayuki Takeda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai

Publication date: 27 September 2021

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

Full work available at URL: https://arxiv.org/abs/1901.10633

zbMATH Keywords

Lyndon wordstriemaximal repetitions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

String covers of a tree

Cites Work

• Unnamed Item
• 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
• A linear-time algorithm for a special case of disjoint set union
• The suffix tree of a tree and minimizing sequential transducers
• String powers in trees
• The maximal number of cubic runs in a word
• Efficient counting of square substrings in a tree
• The Maximum Number of Squares in a Tree
• Computing runs on a trie
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• The “Runs” Theorem

This page was built for publication: Efficiently computing runs on a trie