King's College London

Research portal

Efficient Identification of k-Closed Strings

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

Original languageEnglish
Title of host publicationEngineering Applications of Neural Networks: 18th International Conference, EANN 2017, Athens, Greece, August 25--27, 2017, Proceedings
EditorsGiacomo Boracchi, Lazaros Iliadis, Chrisina Jayne, Aristidis Likas
Place of PublicationCham
PublisherSpringer International Publishing Switzerland
Pages583-595
Number of pages13
Volume744
ISBN (Electronic)978-3-319-65172-9
ISBN (Print)978-3-319-65171-2
DOIs
Publication statusE-pub ahead of print - 2 Aug 2017

King's Authors

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)O(kn) -time and O(n)O(n) -space algorithm to achieve this along with the pseudocode of an implementation.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454