1. Efficient Identification of k-Closed Strings.
- Author
-
Alamro, Hayam, Alzamel, Mai, Iliopoulos, Costas S., Pissis, Solon P., Sung, Wing-Kin, and Watts, Steven
- Subjects
- *
HAMMING distance , *ALGORITHMS , *SUFFIXES & prefixes (Grammar) , *IDENTIFICATION , *INTEGERS - Abstract
A closed string contains a proper factor occurring as both a prefix and a suffix but not elsewhere in the string. Closed strings were introduced by Fici (WORDS 2011) as objects of combinatorial interest. This paper addresses a new problem by extending the closed string problem to the k -closed string problem, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter k. We address the problem of deciding whether or not a given string of length n over an integer alphabet is k -closed and additionally specifying the border resulting in the string being k -closed. Specifically, we present an 𝒪 (k n) -time and 𝒪 (n) -space algorithm to achieve this along with the pseudocode of an implementation and proof-of-concept experimental results. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF