A new characterization of maximal repetitions by Lyndon trees

DOI10.1137/1.9781611973730.38zbMath1372.68216OpenAlexW2949643461MaRDI QIDQ5363085

Yuto Nakashima, Kazuya Tsuruta, Hideo Bannai, Shunsuke Inenaga, Masayuki Takeda, Tomohiro I.

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.38

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15)

Related Items (21)

Lyndon words formalized in Isabelle/HOL ⋮ Prefix-Suffix Square Completion ⋮ Lyndon array construction during Burrows-Wheeler inversion ⋮ Can formal languages help pangenomics to represent and analyze multiple genomes? ⋮ Computing primitively-rooted squares and runs in partial words ⋮ Longest $$\alpha $$-Gapped Repeat and Palindrome ⋮ The “Runs” Theorem ⋮ Numeric Lyndon-based feature embedding of sequencing reads for machine learning approaches ⋮ Unnamed Item ⋮ Dynamic and internal longest common substring ⋮ On the density of Lyndon roots in factors ⋮ Fast computation of abelian runs ⋮ 2D Lyndon words and applications ⋮ On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties ⋮ Optimal bounds for computing \({\alpha}\)-gapped repeats ⋮ Unnamed Item ⋮ Counting maximal-exponent factors in words ⋮ Inverse Lyndon words and inverse Lyndon factorizations of words ⋮ Two-dimensional maximal repetitions ⋮ Small-space LCE data structure with constant-time queries ⋮ Almost linear time computation of maximal repetitions in run length encoded strings

This page was built for publication: A new characterization of maximal repetitions by Lyndon trees