Efficient identification of k-closed strings

Hayam Alamro, Mai Alzamel, Costas S. Iliopoulos, Solon P. Pissis, Steven Watts*, Wing Kin Sung

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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. In this paper, we extend this definition to k-closed strings, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter k. We then address the problem of identifying 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 O(kn)-time and O(n)-space algorithm to achieve this along with the pseudocode of an implementation.

Original languageEnglish
Title of host publicationEngineering Applications of Neural Networks - 18th International Conference, EANN 2017, Proceedings
EditorsLazaros Iliadis, Aristidis Likas, Chrisina Jayne, Giacomo Boracchi
PublisherSpringer Verlag
Pages583-595
Number of pages13
ISBN (Print)9783319651712
DOIs
Publication statusPublished - 1 Jan 2017
Externally publishedYes
Event18th International Conference on Engineering Applications of Neural Networks, EANN 2017 - Athens, Greece
Duration: 25 Aug 201727 Aug 2017

Publication series

NameCommunications in Computer and Information Science
Volume744
ISSN (Print)1865-0929

Conference

Conference18th International Conference on Engineering Applications of Neural Networks, EANN 2017
CountryGreece
CityAthens
Period25/08/1727/08/17

Fingerprint Dive into the research topics of 'Efficient identification of k-closed strings'. Together they form a unique fingerprint.

Cite this