License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2018.19
URN: urn:nbn:de:0030-drops-86913
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8691/
Go to the corresponding LIPIcs Volume Portal

Urabe, Yuki ; Nakashima, Yuto ; Inenaga, Shunsuke ; Bannai, Hideo ; Takeda, Masayuki

Longest Lyndon Substring After Edit

pdf-format:
LIPIcs-CPM-2018-19.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{urabe_et_al:LIPIcs:2018:8691,
  author =	{Yuki Urabe and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda},
  title =	{{Longest Lyndon Substring After Edit}},
  booktitle =	{Annual Symposium on Combinatorial Pattern Matching  (CPM 2018)},
  pages =	{19:1--19:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-074-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{105},
  editor =	{Gonzalo Navarro and David Sankoff and Binhai Zhu},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2018/8691},
  URN =		{urn:nbn:de:0030-drops-86913},
  doi =		{10.4230/LIPIcs.CPM.2018.19},
  annote =	{Keywords: Lyndon word, Lyndon factorization, Lyndon tree, Edit operation}
}

Keywords: Lyndon word, Lyndon factorization, Lyndon tree, Edit operation
Collection: Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
Issue Date: 2018
Date of publication: 18.05.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI