2026-07-23T15:49:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8691 2024-03-06T10:43:02Z ddc:004 open_access

Longest Lyndon Substring After Edit Urabe, Yuki Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki Lyndon word Lyndon factorization Lyndon tree Edit operation The longest Lyndon substring of a string T is the longest substring of T which is a Lyndon word. LLS(T) denotes the length of the longest Lyndon substring of a string T. In this paper, we consider computing LLS(T') where T' is an edited string formed from T. After O(n) time and space preprocessing, our algorithm returns LLS(T') in O(log n) time for any single character edit. We also consider a version of the problem with block edits, i.e., a substring of T is replaced by a given string of length l. After O(n) time and space preprocessing, our algorithm returns LLS(T') in O(l log sigma + log n) time for any block edit where sigma is the number of distinct characters in T. We can modify our algorithm so as to output all the longest Lyndon substrings of T' for both problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuki Urabe and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.19 urn:nbn:de:0030-drops-86913 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.19 eng https://creativecommons.org/licenses/by/3.0/legalcode