DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2024.24

Shortest Cover After Edit

Authors: Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, and Takashi Horiyama

Published in: LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)

Abstract

This paper investigates the (quasi-)periodicity of a string when the string is edited. A string C is called a cover (as known as a quasi-period) of a string T if each character of T lies within some occurrence of C. By definition, a cover of T must be a border of T; that is, it occurs both as a prefix and as a suffix of T. In this paper, we focus on the changes in the longest border and the shortest cover of a string when the string is edited only once. We propose a data structure of size O(n) that computes the longest border and the shortest cover of the string in O(𝓁 log n) time after an edit operation (either insertion, deletion, or substitution of some string) is applied to the input string T of length n, where 𝓁 is the length of the string being inserted or substituted. The data structure can be constructed in O(n) time given string T.

Cite as

Kazuki Mitani, Takuya Mieno, Kazuhisa Seto, and Takashi Horiyama. Shortest Cover After Edit. In 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 296, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mitani_et_al:LIPIcs.CPM.2024.24,
  author =	{Mitani, Kazuki and Mieno, Takuya and Seto, Kazuhisa and Horiyama, Takashi},
  title =	{{Shortest Cover After Edit}},
  booktitle =	{35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-326-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{296},
  editor =	{Inenaga, Shunsuke and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.24},
  URN =		{urn:nbn:de:0030-drops-201345},
  doi =		{10.4230/LIPIcs.CPM.2024.24},
  annote =	{Keywords: string algorithm, border, cover, quasi-periodicity, dynamic string}
}

Search Results

Documents authored by Mitani, Kazuki

Shortest Cover After Edit

Abstract

Cite as

Thanks for your feedback!

Could not send message