A new characterization of maximal repetitions by Lyndon trees

DOI10.1137/1.9781611973730.38MaRDI QIDQ5363085zbMATH OpenOpenAlexFDO

Authors Hideo Bannai, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, Kazuya Tsuruta, 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)

Recommendations

• The ``runs theorem
• Maximal repetitions in strings
• The runs theorem and beyond
• Analysis of Maximal Repetitions in Strings
• Fast and Practical Algorithms for Computing All the Runs in a String

Cited in

(25)

• Efficiently computing runs on a trie
• On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties
• Optimal bounds for computing \({\alpha}\)-gapped repeats
• Lyndon words formalized in Isabelle/HOL
• scientific article; zbMATH DE number 7559170 (Why is no real title available?)
• Lyndon array construction during Burrows-Wheeler inversion
• Counting maximal-exponent factors in words
• Two-dimensional maximal repetitions
• Dynamic and internal longest common substring
• Fast computation of abelian runs
• Two-dimensional maximal repetitions
• Can formal languages help pangenomics to represent and analyze multiple genomes?
• Small-space LCE data structure with constant-time queries
• Numeric Lyndon-based feature embedding of sequencing reads for machine learning approaches
• Computing primitively-rooted squares and runs in partial words
• Almost linear time computation of maximal repetitions in run length encoded strings
• Prefix-suffix square completion
• Exact and inexact search for 2d side-sharing tandems
• The ``runs theorem
• Reconstructing a string from its Lyndon arrays
• On the density of Lyndon roots in factors
• 2D Lyndon words and applications
• Longest \(\alpha \)-gapped repeat and palindrome
• Cartesian and Lyndon trees
• Inverse Lyndon words and inverse Lyndon factorizations of words

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

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