Efficient Identification of k -Closed Strings
International Journal of Foundations of Computer Science , Volume 31 - Issue 5 p. 595- 610
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 (kn)-time and (n)-space algorithm to achieve this along with the pseudocode of an implementation and proof-of-concept experimental results.
|Algorithms on strings, border, closed string, combinatorics on words, Hamming distance|
|International Journal of Foundations of Computer Science|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam, The Netherlands|
Alamro, H, Alzamel, M, Iliopoulos, C.S, Pissis, S, Sung, W.-K, & Watts, S. (2020). Efficient Identification of k -Closed Strings. International Journal of Foundations of Computer Science, 31(5), 595–610. doi:10.1142/S0129054120500288