Title: A new characterization of maximal repetitions by Lyndon trees
Abstract: Previous chapter Next chapter Full AccessProceedings Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)A new characterization of maximal repetitions by Lyndon treesHideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya TsurutaHideo Bannai, Tomohiro I, Shunsuke Inenaga, Yuto Nakashima, Masayuki Takeda, and Kazuya Tsurutapp.562 - 571Chapter DOI:https://doi.org/10.1137/1.9781611973730.38PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract We give a new characterization of maximal repetitions (or runs) in strings, using a tree defined on recursive standard factorizations of Lyndon words, called the Lyndon tree. The characterization leads to a remarkably simple novel proof of the linearity of the maximum number of runs ρ(n) in a string of length n. Furthermore, we show an upper bound of ρ(n) < 1.5n, which improves on the best upper bound 1.6n (Crochemore & Ilie 2008) that does not rely on computational verification. The proof also gives rise to a new, conceptually simple linear-time algorithm for computing all the runs in a string. A notable characteristic of our algorithm is that, unlike all existing linear-time algorithms, it does not utilize the Lempel-Ziv factorization of the string. Previous chapter Next chapter RelatedDetails Published:2015ISBN:978-1-61197-374-7eISBN:978-1-61197-373-0 https://doi.org/10.1137/1.9781611973730Book Series Name:ProceedingsBook Code:PRDA15Book Pages:viii + 2048
Publication Year: 2014
Publication Date: 2014-12-22
Language: en
Type: preprint
Indexed In: ['crossref']
Access and Citation
Cited By Count: 18
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot