References & Citations
Computer Science > Data Structures and Algorithms
Title: Shortest cover after edit
(Submitted on 27 Feb 2024 (v1), last revised 26 Apr 2024 (this version, v2))
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(\ell \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 $\ell$ is the length of the string being inserted or substituted. The data structure can be constructed in $O(n)$ time given string $T$.
Submission history
From: Takuya Mieno [view email][v1] Tue, 27 Feb 2024 11:41:56 GMT (424kb,D)
[v2] Fri, 26 Apr 2024 03:05:06 GMT (453kb,D)
Link back to: arXiv, form interface, contact.