Efficiently computing runs on a trie

DOI10.1016/J.TCS.2021.07.011OpenAlexW3184027729MaRDI QIDQ820550FDOQ820550

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

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?

zbMATH Keywords

Lyndon wordstriemaximal repetitions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Title not available (Why is that?)
• 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
• Longest common extensions in trees
• Extracting powers and periods in a word from its runs structure
• Title not available (Why is that?)
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• The maximum number of squares in a tree
• The “Runs” Theorem
• Title not available (Why is that?)
• The maximal number of cubic runs in a word
• String powers in trees
• Efficient counting of square substrings in a tree
• Computing runs on a trie

Cited In (4)

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

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)