Search

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 [Formula: see text]-closed string problem, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter [Formula: see text]. We address the problem of deciding whether or not a given string of length [Formula: see text] over an integer alphabet is [Formula: see text]-closed and additionally specifying the border resulting in the string being [Formula: see text]-closed. Specifically, we present an [Formula: see text]-time and [Formula: see text]-space algorithm to achieve this along with the pseudocode of an implementation and proof-of-concept experimental results.

A border of a string is a prefix of the string that is simultaneously its suffix. It is one of the basic stringology keystones used as a part of many algorithms in pattern matching, molecular biology, computer-assisted music analysis and others. The paper offers the automata-theoretical description of Iliopoulos's ALL_BORDERS algorithm. The algorithm finds all borders of a string with don't care symbols. We show that ALL_BORDERS algorithm is an implementation of a finite state transducer of specific form. We describe how such a transducer can be constructed and what should be the input string like. The described transducer finds a set of lengths of all borders. Last but not least, we define approximate borders and show how to find all approximate borders of a string when we concern Hamming distance definition. Our solution of this problem is based on transducers again. This allows us to use analogy with automata-based pattern matching methods. Finally we discuss conditions under which the same principle can be used for other distance measures.

Recently, there has been a surge of interest in gapped q-gram filters for approximate string matching. Important design parameters for filters are for example the value of q, the filter-threshold and in particular the shape (aka seed) of the filter. A good choice of parameters can improve the performance of a q-gram filter by orders of magnitude and optimizing these parameters is a nontrivial combinatorial problem. We describe a new method for analyzing gapped q-gram filters. This method is simple and generic. It applies to a variety of filters, overcomes many restrictions that are present in existing algorithms and can easily be extended to new filter variants. To implement our approach, we use an extended version of BDDs (Binary Decision Diagrams), a data structure that efficiently represents sets of bit-strings. In a second step, we define a new class of multi-shape filters and analyze these filters with the BDD-based approach. Experiments show that multi-shape filters can outperform the best single-shape filters, which are currently in use, in many aspects. The BDD-based algorithm is crucial for the design and analysis of these new and better multi-shape filters. Our results apply to the k-mismatches problem, i.e. approximate string matching with Hamming distance.

Let [Formula: see text] be a dictionary consisting of n binary strings of length m each, represented as a trie. The usual d-query asks if there exists a string in [Formula: see text] within Hamming distance d of a given binary query string q. We present a simple algorithm to determine if there is a member in [Formula: see text] within edit distanced of a given query string q of length m. The method takes time O(dmd+1) in the RAM model, independent of n, and requires O(dm) additional space. We also generalize the results for the case of the problem over a larger alphabet.