Efficiently computing runs on a trie

DOI10.1016/J.TCS.2021.07.011MaRDI QIDQ820550OpenAlexFDO

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

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)

Recommendations

• Fast and Practical Algorithms for Computing All the Runs in a String
• The ``runs theorem
• The number of runs in a string
• A new characterization of maximal repetitions by Lyndon trees
• How many runs can a string contain?

Cites work

• scientific article; zbMATH DE number 5717191 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 1522932 (Why is no real title available?)
• A linear-time algorithm for a special case of disjoint set union
• Computing runs on a trie
• Efficient counting of square substrings in a tree
• Extracting powers and periods in a word from its runs structure
• Longest common extensions in trees
• String powers in trees
• The ``runs theorem
• The level ancestor problem simplified
• The maximal number of cubic runs in a word
• The maximum number of squares in a tree
• The suffix tree of a tree and minimizing sequential transducers
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE

Cited in

(4)

• String covers of a tree revisited
• Computing runs on a trie
• Counting subwords using a trie automaton
• String covers of a tree

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

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