Search

String matching is one of the most extensively studied problems in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last few decades a myriad of alternative solutions have been proposed, based on very different techniques. However, automata have always played a very important role in the design of efficient string matching algorithms. In this paper we present the Range Automaton , a weak yet efficient variant of the non-deterministic suffix automaton of a string whose configuration can be encoded in a very simple form and which is particularly suitable to be used for solving a multitude of text-searching problems. We will firstly develop our approach in the case of exact string matching and present an efficient algorithm, named Backward Range Automaton Matcher, which turns out to be very fast in many practical cases. Later, we will show how the Range Automaton can be adapted in an effective way also to non-standard string matching problems such as swap matching and multiple string matching. Experimental results suggest that our approach is flexible and effective for all three search problems addressed, especially in the case of long patterns. • We present a simple and efficient technique for simulating the suffix automaton of a string. • The new technique leads to the definition of an automaton, called Range Automaton, for the weak recognition of the suffixes of a string. • We apply the Range Automaton to the exact string matching problem, obtaining an efficient and flexible solution in practice, especially in the case of long patterns. • We extend the application of the Range Automaton to the swap matching problem, a special case of approximate string matching. • We extend the application of the Range Automaton to the problem of multiple pattern matching. [ABSTRACT FROM AUTHOR]

The classic string indexing problem is to preprocess a string S into a compact data structure that supports efficient subsequent pattern matching queries, that is, given a pattern string P , report all occurrences of P within S. In this paper, we study a basic and natural extension of string indexing called the string indexing for top- k close consecutive occurrences problem (Sitcco). Here, a consecutive occurrence is a pair (i , j) , i < j , such that P occurs at positions i and j in S and there is no occurrence of P between i and j , and their distance is defined as j − i. Given a pattern P and a parameter k , the goal is to report the top- k consecutive occurrences of P in S of minimal distance. The challenge is to compactly represent S while supporting queries in time close to the length of P and k. We give three time-space trade-offs for the problem. Let n be the length of S , m the length of P , and ϵ ∈ (0 , 1 ]. Our first result achieves O (n log ⁡ n) space and optimal query time of O (m + k). Our second and third results achieve linear space and query times either O (m + k 1 + ϵ) or O (m + k log 1 + ϵ ⁡ n). Along the way, we develop several techniques of independent interest, including a new translation of the problem into a line segment intersection problem and a new recursive clustering technique for trees. [ABSTRACT FROM AUTHOR]

Pattern matching with wildcards is a string matching problem with the goal of finding all factors of a text t of length n that match a pattern x of length m , where wildcards (characters that match everything) may be present. In this paper we present a number of complexity results and fast average-case algorithms for pattern matching where wildcards are allowed in the pattern, however, the results are easily adapted to the case where wildcards are allowed in the text as well. We analyse the average-case complexity of these algorithms and derive non-trivial time bounds. These are the first results on the average-case complexity of pattern matching with wildcards which provide a provable separation in time complexity between exact pattern matching and pattern matching with wildcards. We introduce the wc-period of a string which is the period of the binary mask x b where x b [ i ] = a iff x [ i ] ≠ ϕ and b otherwise. We denote the length of the wc-period of a string x by ▪. We show the following results for constant 0 < ϵ < 1 and a pattern x of length m and g wildcards with ▪ the prefix of length p contains g p wildcards: • If lim m → ∞ ⁡ g p p = 0 there is an optimal algorithm running in O (n log σ ⁡ m m) -time on average. • If lim m → ∞ ⁡ g p p = 1 − ϵ there is an algorithm running in O (n log σ ⁡ m log 2 ⁡ p m) -time on average. • If lim m → ∞ ⁡ g m = lim m → ∞ ⁡ 1 − f (m) = 1 any algorithm takes at least Ω (n log σ ⁡ m f (m)) -time on average. [ABSTRACT FROM AUTHOR]

The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a text string T of length n has O (n) nodes and edges, and the string label of each edge is encoded by a pair of positions in T. Thus, even after the tree is built, the input string T needs to be kept stored and random access to T is still needed. The linear-size suffix tries (LSTs), proposed by Crochemore et al. [Linear-size suffix tries, TCS 638:171-178, 2016], are a "stand-alone" alternative to the suffix trees. Namely, the LST of an input text string T of length n occupies O (n) total space, and supports pattern matching and other tasks with the same efficiency as the suffix tree without the need to store the input text string T. Crochemore et al. proposed an offline algorithm which transforms the suffix tree of T into the LST of T in O (n log ⁡ σ) time and O (n) space, where σ is the alphabet size. In this paper, we present two types of online algorithms which "directly" construct the LST, from right to left, and from left to right, without constructing the suffix tree as an intermediate structure. Both algorithms construct the LST incrementally when a new symbol is read, and do not access the previously read symbols. Both of the right-to-left construction algorithm and the left-to-right construction algorithm work in O (n log ⁡ σ) time and O (n) space. The main feature of our algorithms is that the input text string does not need to be stored. [ABSTRACT FROM AUTHOR]

The Simon's congruence problem is to determine whether or not two strings have the same set of subsequences of length no greater than a given integer, and the problem can be answered in linear time. We consider the Simon's congruence pattern matching problem that looks for all substrings of a text that are congruent to a pattern under the Simon's congruence. We propose a linear time algorithm by reusing results from previous computations with the help of new data structures called X-trees and Y-trees. Moreover, we investigate several variants of the problem such as identifying the shortest substring or subsequence of the text that is congruent to the pattern under the Simon's congruence, or finding frequent matchings. We design efficient algorithms for these problems. We conclude the paper with two open problems: finding the longest congruent subsequence and optimizing the pattern matching problem. • A polynomial algorithm linear in the length of the text that computes all substrings of the text that is Simon's k-congruent to the pattern. • Efficient algorithms that solve variants of the Simon's congruence pattern matching problem. • A data structure with linear preprocessing time that answers two types of queries related to Simon's congruence pattern matching multiplicities. [ABSTRACT FROM AUTHOR]

Given a two-dimensional array of symbols and a picture language over a finite alphabet, we investigate how to find rectangular subarrays that belong to the picture language. Two-dimensional pattern matching problems can be formulated by interpreting subarrays as matches and picture languages as patterns. We formulate four particular problems – finding maximum, minimum, any or all match(es) – and describe algorithms solving the problems for basic classes of picture languages, which include local picture languages and picture languages accepted by various types of deterministic two-dimensional finite automata such as four-way, three-way and two-way automata, on-line tessellation automata, and returning finite automata. We also prove that the pattern matching problems cannot be solved for the class of local picture languages in time linear in the input area unless the well known problem of triangle finding in a graph is solvable in quadratic time. This shows a fundamental difference between the complexity of one-dimensional and two-dimensional pattern matching. [ABSTRACT FROM AUTHOR]

We give approximation algorithms for matching two sets of line segments in constant dimension. We consider several versions of the problem: Hausdorff distance, bottleneck distance and largest common subset. We study these similarity measures under several sets of transformations: translations in arbitrary dimension, rotations about a fixed point and rigid motions in two dimensions. As opposed to previous theoretical work on this problem, we match segments individually, in other words we regard our two input sets as sets of segments rather than unions of segments. [ABSTRACT FROM AUTHOR]

Indexing labeled graphs for pattern matching is a central challenge of pangenomics. Equi et al. (2022) [14] developed the Elastic Founder Graph (EFG) representing an alignment of m sequences of length n , drawn from alphabet Σ plus the special gap character: the paths spell the original sequences or their recombination. By enforcing the semi-repeat-free property, the EFG admits a polynomial-space index for linear-time pattern matching, breaking through the conditional lower bounds on indexing labeled graphs (Equi et al. [13]). In this work, we improve the space of the EFG index answering pattern matching queries in linear time, from linear in the length of all strings spelled by three consecutive node labels, to linear in the size of the edge labels. Then, we develop linear-time construction algorithms optimizing for different metrics: we improve the existing linearithmic construction algorithms to O (m n) , by solving the novel exclusive ancestor set problem on trees; we propose, for the simplified gapless setting, an O (m n) -time solution minimizing the maximum block height, that we generalize by substituting block height with prefix-aware height. Finally, to show the versatility of the framework, we develop a BWT-based EFG index and study how to encode and perform document listing queries on a set of paths of the graphs, reporting which paths present a given pattern as a substring. We propose the EFG framework as an improved and enhanced version of the framework for the gapless setting, along with construction methods that are valid in any setting concerned with the segmentation of aligned sequences. [ABSTRACT FROM AUTHOR]

Dictionary Matching is a variant of the Pattern Matching problem where multiple patterns are simultaneously matched to a single text. In case where the patterns contain sequences of don't care symbols, the problem is called Dictionary Matching with Gaps. The problem is related to cyber security, where the patterns represent the malware sequences we want to detect in the text, which may appear in several packets. Another famous variant of Pattern matching is the Parameterized Matching, where two equal-length strings are a parameterized match if there exists a bijection on the alphabets, such that one string matches the other under the bijection. In this paper the problem of Parameterized Dictionary Matching with One Gap is described, which is an extension of the Dictionary Matching with Gaps, where the parameterized match serves as encryption system of the malware sequences. The paper presents two algorithms solving the Parameterized Dictionary Matching with One Gap, for dictionaries with non-uniformly bounded gaps. The first solves the problem with a query time of O (| T | δ m a x log 2 ⁡ d + o c c) , while the second solution has a query time of O (| T | δ m a x + o c c) , where | T | is the size of the text, d is the number of gapped patterns in the dictionary, δ m a x is the difference between the highest upper bound and the lowest lower bound of the gaps and occ is the number of the gapped patterns reported as output. We also suggest the related problem of Parameterized Dictionary Recognition with One Gap, which requires reporting a single parameterized appearance of each gapped pattern. This is of interest in case we want only to know which malware sequences where detected in the text, and not the details of all their appearances in the text, that may be numerous. We present similar algorithms for this problem as well. [ABSTRACT FROM AUTHOR]

A skeleton Huffman tree is a Huffman tree from which all full subtrees of depth h ≥ 1 have been pruned. Skeleton Huffman trees are used to save storage and enhance processing time in several applications such as decoding, compressed pattern matching and wavelet trees for random access. A reduced skeleton tree prunes the skeleton Huffman tree further to an even smaller tree. The resulting more compact trees can be used to further enhance the time and space complexities of the corresponding algorithms. However, it is shown that the straightforward ways of basing the constructions of a skeleton tree as well as that of a reduced skeleton tree on a canonical Huffman tree do not necessarily yield the least number of nodes. New algorithms for achieving such trees are given. [ABSTRACT FROM AUTHOR]

We study the online Parameterized Dictionary Matching with One Gap problem (PDMOG) which is the following. Preprocess a dictionary D of d patterns, where each pattern contains a special gap symbol that can match any string, so that given a text T arriving online, a character at a time, we can report all the patterns from D that parameterized match to suffixes of the text that has arrived so far, before the next character arrives. Two equal-length strings are a parameterized match if there exists a bijection on the alphabets, such that one string matches the other under the bijection. The gap symbols are associated with bounds determining the possible lengths of matching strings. Online Dictionary Matching with One Gap (DMOG) captures the difficulty in a bottleneck procedure for cyber-security, as many digital signatures of viruses manifest themselves as patterns with a single gap. Parameterized match captures possible encryption of the patterns. We also define the strict PDMOG problem, in which subpatterns of the same dictionary pattern should be parameterized matched via the same bijection. This captures situations where subpatterns of a dictionary pattern are encoded simultaneously. We study this problem for special case called alphabet-saturated dictionairy , where every subpattern contains all characters of the dictionary alphabet Σ. We use the following parameters to describe our results: D is the total size of the dictionary (not including the gaps), plsc is the longest parameterized suffix chain of subpatterns in D , op is the number of parameterized patterns occurrences in T , α ⁎ and β ⁎ are the minimum left and maximum right gap borders in the non-uniformly bounded dictionary case, δ (G D) is the degeneracy of the graph G D representing dictionary D. This graph is classified as sparse or dense according the value of the δ (G D) and plsc parameters. We obtain: – O ˜ (D) preprocessing time/space and O ˜ (δ (G D) ⋅ plsc + plsc ⋅ max ⁡ { | Σ | , M } + o p) query time per text character algorithm for online PDMOG with sparse graph dictionaries. – O ˜ (D + d (β ⁎ − α ⁎)) preprocessing time/space and O ˜ ( plsc ⋅ d ⋅ (β ⁎ − α ⁎) + plsc ⋅ max ⁡ { | Σ | , M } + o p) query time per text character algorithm for online PDMOG with dense graph dictionaries. – O ˜ (D) preprocessing time/space and O ˜ (δ (G D) ⋅ plsc + o p) query time per text character algorithm for strict PDMOG with alphabet-saturated dictionaries. These results are parallel to the ones obtained for the Dictionary with One Gap (DMOG) problem almost matching the lower bounds achieved for this problem [7]. While the parameter δ (G D) can be as large as d and much lager if the dictionary has non-uniform gap boundaries, and the parameter plsc could theoretically be as large as d , in many practical situations these parameters are actually small. The strength of our work is in achieving results that explore and exploit small values for these parameters, thus supplying algorithms that are suitable for some practical cyber security needs. [ABSTRACT FROM AUTHOR]

We introduce a new metric of match, called Cartesian tree matching , which means that two strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we define single pattern matching, multiple pattern matching, and indexing problems. We propose a linear time algorithm for single pattern matching, and randomized linear time algorithms for multiple pattern matching and indexing. We also define three types of periods, called full period, initial period, and general period. We propose O (n) time, O (n log ⁡ log ⁡ n) time, and O (n log ⁡ n) time algorithms for finding all the full periods, initial periods, and general periods of a string of length n , respectively. Our efficient algorithms use a representation of the Cartesian tree, called parent-distance representation. [ABSTRACT FROM AUTHOR]

• Prefix normal words form a bubble language. • All prefix normal words of length n can be generated in combinatorial Gray code order. • The new generation algorithm runs in amortized time O (log 2 n) per word. • We present a new view of bubble languages. • We pose several open problems on prefix normal words. A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. By proving that the set of prefix normal words is a bubble language, we can exhaustively list all prefix normal words of length n as a combinatorial Gray code, where successive strings differ by at most two swaps or bit flips. This Gray code can be generated in O (log 2 ⁡ n) amortized time per word, while the best generation algorithm hitherto has O (n) running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages. [ABSTRACT FROM AUTHOR]

The expressiveness of communication primitives has been explored in a common framework based on the π -calculus by considering four features: synchronism (asynchronous vs synchronous), arity (monadic vs polyadic data), communication medium (shared dataspaces vs channel-based), and pattern-matching (binding to a name vs testing name equality). Here pattern-matching is generalised to account for terms with internal structure such as in recent calculi like Spi calculi, Concurrent Pattern Calculus and Psi calculi. This paper explores intensionality , a feature that extends pattern-matching to allow communication primitives to interact by also matching on the structure of terms. By means of possibility/impossibility of encodings, this paper shows that intensionality alone can encode synchronism, arity, communication-medium, and pattern-matching, yet no combination of these without intensionality can encode any intensional language. Further, some languages may also be non-linear, where two inputs must be equal to allow interaction. This paper also explores all the relations between linear and non-linear variations of the above languages. [ABSTRACT FROM AUTHOR]

Tree pattern matching on ordered trees is an important problem in Computer Science. Ordered trees can be represented as strings with additional properties via various linearisations. We present a backward tree pattern matching algorithm for ordered trees for various linear representations of trees and tree patterns. The algorithm adaptations find all occurrences of a single given tree pattern which match an input tree regardless of the chosen linearisation. The algorithms preserve the properties and advantages of standard backward string pattern matching using Boyer-Moore-Horspool's bad character shift heuristics. The number of symbol comparisons in the backward tree pattern matching can be sublinear in the size of the input tree. As in the case of the string version of Boyer-Moore-Horspool's matching algorithm, the size of the bad character shift table used by the algorithm is linear in the size of the alphabet. We compare the algorithm adaptations with the algorithm using originally chosen linear representation and with the best performing previously existing algorithms based on (non-linearised) tree pattern matching using finite tree automata or stringpath matchers. We show that the presented backward tree pattern matching algorithms outperform the non-linearising ones for single pattern matching and they perform among themselves comparably. [ABSTRACT FROM AUTHOR]

An elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent a multiple alignment of several closely-related sequences (e.g., pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length m in an elastic-degenerate text. There exists a non-combinatorial O (n m 1.381 + N) -time algorithm to solve this problem on-line [1]. In this paper, we study the same problem under the edit distance model and present an O (k 2 m G + k N) -time and O (m) -space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O (k m G + k N) -time and O (m) -space algorithm for solving the problem under Hamming distance. [ABSTRACT FROM AUTHOR]

The observed frequency of the longest proper prefix, the longest proper suffix, and the longest infix of a word w in a given sequence x can be used for classifying w as avoided or overabundant. The definitions used for the expectation and deviation of w in this statistical model were described and biologically justified by Brendel et al. (1986) [1]. We have very recently introduced a time-optimal algorithm for computing all avoided words of a given sequence over an integer alphabet (2017) [2]. In this article, we extend this study by presenting an O (n) -time and O (n) -space algorithm for computing all overabundant words in a sequence x of length n over an integer alphabet. Our main result is based on a new non-trivial combinatorial property of the suffix tree T of x : the number of distinct factors of x whose longest infix is the label of an explicit node of T is no more than 3 n − 4. We further show that the presented algorithm is time-optimal by proving that O (n) is a tight upper bound for the number of overabundant words. Finally, we present experimental results, using both synthetic and real data, which justify the effectiveness and efficiency of our approach in practical terms. [ABSTRACT FROM AUTHOR]

The dictionary matching is a task to find all occurrences of pattern strings in a set D (called a dictionary) on a text string T. The Aho–Corasick-automaton (AC-automaton) which is built on D is a fundamental data structure which enables us to solve the dictionary matching problem in O (d log ⁡ σ) preprocessing time and O (n log ⁡ σ + occ) matching time, where d is the total length of the patterns in the dictionary D , n is the length of the text, σ is the alphabet size, and occ is the total number of occurrences of all the patterns in the text. The dynamic dictionary matching is a variant where patterns may dynamically be inserted into and deleted from the dictionary D. This problem is called semi-dynamic dictionary matching if only insertions are allowed. In this paper, we propose two efficient algorithms that can solve both problems with some modifications. For a pattern of length m , our first algorithm supports insertions in O (m log ⁡ σ + log ⁡ d / log ⁡ log ⁡ d) time and pattern matching in O (n log ⁡ σ + occ) for the semi-dynamic setting. This algorithm also supports both insertions and deletions in O (σ m + log ⁡ d / log ⁡ log ⁡ d) time and pattern matching in O (n (log ⁡ d / log ⁡ log ⁡ d + log ⁡ σ) + occ (log ⁡ d / log ⁡ log ⁡ d)) time for the dynamic dictionary matching problem by some modifications. This algorithm is based on the directed acyclic word graph (DAWG) of Blumer et al. (JACM 1987). Our second algorithm, which is based on the AC-automaton, supports insertions in O (m log ⁡ σ + u f + u o) time for the semi-dynamic setting and supports both insertions and deletions in O (σ m + u f + u o) time for the dynamic setting, where u f and u o respectively denote the numbers of states in which the failure function and the output function need to be updated. This algorithm performs pattern matching in O (n log ⁡ σ + occ) time for both settings. Our algorithm achieves optimal update time for AC-automaton based methods over constant-size alphabets, since any algorithm which explicitly maintains the AC-automaton requires Ω (m + u f + u o) update time. • Two algorithms for dynamic dictionary matching are presented. • An Aho–Corasick automata based algorithm with optimal update time is proposed. • Tight lower and upper bounds for updating directed acyclic word graphs are given. [ABSTRACT FROM AUTHOR]

The string matching problem on a node-labeled graph G = (V , E) asks whether a given pattern string P equals the concatenation of node labels of some path in G. This is a basic primitive in various problems in bioinformatics, graph databases, or networks, and it was recently proven that solving it in time O (| E | 1 − ϵ | P |) or O (| E | | P | 1 − ϵ) is hard under OVH , the Orthogonal Vectors Hypothesis, and thus under SETH , the Strong Exponential Time Hypothesis (Equi et al., 2019 [11]). We consider its indexed version, where the graph is indexed to support string queries. We show that, under OVH , no polynomial-time index of the graph performed in time O (| E | α) can support querying P in time O (| P | + | E | δ | P | β) , with either δ < 1 or β < 1. We present our techniques as a general framework, introducing the notion of linear independent-components (lic) reduction , from which we derive our result. This allows us to also translate the quadratic conditional lower bound of Backurs and Indyk (2015) [48] for the problem of matching a query string inside a text, under edit distance, into an analogous tight quadratic lower bound for its indexed version. This improves the recent result of Cohen-Addad, Feuilloley and Starikovskaya (2019) [49] , with a slightly different boundary condition. We also apply our technique to obtain the first quadratic indexing lower bounds for Fréchet distance and rooted unlabeled subtree-isomorphism queries. [ABSTRACT FROM AUTHOR]

Path polymorphism enables the definition of functions uniformly applicable to arbitrary recursively specified data structures. Path polymorphic function declarations rely on patterns of the form x y (i.e. the application of two variables), which decompose a data structure into its parts. We propose a static type system for a calculus that captures this feature, combining constants as types, union types and recursive types. The fundamental properties of Subject Reduction and Progress are addressed to guarantee well-behaved dynamics; they rely crucially on a novel notion of pattern compatibility. We also introduce an efficient type-checking algorithm by formulating a syntax-directed variant of the type system. This involves algorithms for checking type equivalence and subtyping, both based on coinductive characterizations of those relations. [ABSTRACT FROM AUTHOR]

In a simple pattern matching problem one has a pattern w and a text t , which are words over a finite alphabet Σ. One may ask whether w occurs in t , and if so, where? More generally, we may have a set P of patterns and a set T of texts, where P and T are regular languages. We are interested whether any word of T begins with a word of P , ends with a word of P , has a word of P as a factor, or has a word of P as a subsequence. Thus we are interested in the languages (P Σ ⁎) ∩ T , (Σ ⁎ P) ∩ T , (Σ ⁎ P Σ ⁎) ∩ T , and Image 1 , where Image 2 is the shuffle operation. The state complexity κ (L) of a regular language L is the number of states in the minimal deterministic finite automaton recognizing L. We derive the following upper bounds on the state complexities of our pattern-matching languages, where κ (P) ⩽ m , and κ (T) ⩽ n : κ ((P Σ ⁎) ∩ T) ⩽ m n ; κ ((Σ ⁎ P) ∩ T) ⩽ 2 m − 1 n ; κ ((Σ ⁎ P Σ ⁎) ∩ T) ⩽ (2 m − 2 + 1) n ; and Image 3. We prove that these bounds are tight, and that to meet them, the alphabet must have at least two letters in the first three cases, and at least m − 1 letters in the last case. [ABSTRACT FROM AUTHOR]

Abstract We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of size N over alphabet [ 1 , σ ] is composed of D copies of a string of size n , and s edits are applied on ranges of copies. We introduce the first document listing index with size O ˜ (n + s) , precisely O ((n lg ⁡ σ + s lg 2 ⁡ N) lg ⁡ D) bits, and with useful worst-case time guarantees: Given a pattern of length m , the index reports the ndoc > 0 strings where it appears in time O (m lg 1 + ϵ ⁡ N ⋅ ndoc) , for any constant ϵ > 0 (and tells in time O (m lg ⁡ N) if ndoc = 0). Our technique is to augment a range data structure that is commonly used on grammar-based indexes, so that instead of retrieving all the pattern occurrences, it computes useful summaries on them. We show that the idea has independent interest: we introduce the first grammar-based index that, on a text T [ 1 , N ] with a grammar of size r , uses O (r lg ⁡ N) bits and counts the number of occurrences of a pattern P [ 1 , m ] in time O (m 2 + m lg 2 + ϵ ⁡ r) , for any constant ϵ > 0. We also give the first index using O (z lg ⁡ (N / z) lg ⁡ N) bits, where T is parsed by Lempel–Ziv into z phrases, counting occurrences in time O (m lg 2 + ϵ ⁡ N). [ABSTRACT FROM AUTHOR]

Given a string S , the compressed indexing problem is to preprocess S into a compressed representation that supports fast substring queries . The goal is to use little space relative to the compressed size of S while supporting fast queries. We present a compressed index based on the Lempel–Ziv 1977 compression scheme. We obtain the following time–space trade-offs: For constant-sized alphabets (i) O ( m + occ lg ⁡ lg ⁡ n ) time using O ( z lg ⁡ ( n / z ) lg ⁡ lg ⁡ z ) space, or (ii) O ( m ( 1 + lg ϵ ⁡ z lg ⁡ ( n / z ) ) + occ ( lg ⁡ lg ⁡ n + lg ϵ ⁡ z ) ) time using O ( z lg ⁡ ( n / z ) ) space, For integer alphabets polynomially bounded by n (iii) O ( m ( 1 + lg ϵ ⁡ z lg ⁡ ( n / z ) ) + occ ( lg ⁡ lg ⁡ n + lg ϵ ⁡ z ) ) time using O ( z ( lg ⁡ ( n / z ) + lg ⁡ lg ⁡ z ) ) space, or (iv) O ( m + occ ( lg ⁡ lg ⁡ n + lg ϵ ⁡ z ) ) time using O ( z ( lg ⁡ ( n / z ) + lg ϵ ⁡ z ) ) space, where n and m are the length of the input string and query string respectively, z is the number of phrases in the LZ77 parse of the input string, occ is the number of occurrences of the query in the input and ϵ > 0 is an arbitrarily small constant. In particular, (i) improves the leading term in the query time of the previous best solution from O ( m lg ⁡ m ) to O ( m ) at the cost of increasing the space by a factor lg ⁡ lg ⁡ z . Alternatively, (ii) matches the previous best space bound, but has a leading term in the query time of O ( m ( 1 + lg ϵ ⁡ z lg ⁡ ( n / z ) ) ) . However, for any polynomial compression ratio, i.e., z = O ( n 1 − δ ) , for constant δ > 0 , this becomes O ( m ) . Our index also supports extraction of any substring of length ℓ in O ( ℓ + lg ⁡ ( n / z ) ) time. Technically, our results are obtained by novel extensions and combinations of existing data structures of independent interest, including a new batched variant of weak prefix search. [ABSTRACT FROM AUTHOR]

An exact run in a string T is a non-empty substring of T that is a repetition of a smaller substring possibly followed by a prefix of it. Finding maximal exact runs in strings is an important problem and therefore a well-studied one in the area of stringology. For a given string T of length n , finding all maximal exact runs in the string can be done in O ( n log ⁡ n ) time on general ordered alphabets or O ( n ) time on integer alphabets. In this paper, we investigate the maximal approximate runs problem: for a given string T and a number k , find non-empty substrings T ′ of T such that changing at most k letters in T ′ transforms them into a maximal exact run. We present an O ( n k 2 log 2 ⁡ k + o c c ) algorithm to solve this problem, where occ is the number of substrings found. [ABSTRACT FROM AUTHOR]

The famous Burrows–Wheeler Transform (BWT) was originally defined for a single string but variations have been developed for sets of strings, labeled trees, de Bruijn graphs, etc. In this paper we propose a framework that includes many of these variations and that we hope will simplify the search for more. We first define Wheeler graphs and show they have a property we call path coherence . We show that if the state diagram of a finite-state automaton is a Wheeler graph then, by its path coherence, we can order the nodes such that, for any string, the nodes reachable from the initial state or states by processing that string are consecutive. This means that even if the automaton is non-deterministic, we can still store it compactly and process strings with it quickly. We then rederive several variations of the BWT by designing straightforward finite-state automata for the relevant problems and showing that their state diagrams are Wheeler graphs. [ABSTRACT FROM AUTHOR]

A 1-prefix normal word is a binary word with the property that no factor has more 1s than the prefix of the same length; a 0-prefix normal word is defined analogously. These words arise in the context of indexed binary jumbled pattern matching, where the aim is to decide whether a word has a factor with a given number of 1s and 0s (a given Parikh vector). Each binary word has an associated set of Parikh vectors of the factors of the word. Using prefix normal words, we provide a characterization of the equivalence class of binary words having the same set of Parikh vectors of their factors. We prove that the language of prefix normal words is not context-free and is strictly contained in the language of pre-necklaces, which are prefixes of powers of Lyndon words. We give enumeration results on pnw ( n ) , the number of prefix normal words of length n , showing that, for sufficiently large n , 2 n − 4 n lg ⁡ n ≤ pnw ( n ) ≤ 2 n − lg ⁡ n + 1 . For fixed density (number of 1s), we show that the ordinary generating function of the number of prefix normal words of length n and density d is a rational function. Finally, we give experimental results on pnw ( n ) , discuss further properties, and state open problems. [ABSTRACT FROM AUTHOR]

In this paper we investigate jumbled (Abelian) versions of three classical strings problems. In all these problems we assume the input string S [ 1 . . n ] is given in its run-length format S ′ [ 1 . . r ] . The Jumbled Indexing problem is the problem of indexing a string S ′ [ 1 . . r ] over | Σ | for histogram queries, i.e. given a pattern P , we want to find all substrings of S that are permutations of P . We provide an algorithm that constructs an index of size O ( r 2 | Σ | ) in time O ( r 2 ( log ⁡ r + | Σ | log ⁡ | Σ | ) ) , which allows answering histogram queries in O ( | Σ | 3 log ⁡ r ) -time. The Jumbled Border problem is the problem of finding for every location j in S , the longest proper prefix of S [ 1 . . j ] that is also a permutation of a proper suffix of S [ 1 . . j ] , if such exists. We provide an algorithm that solves this problem in O ( | Σ | ( r 2 + n ) ) time, and O ( | Σ | n ) space. A Jumbled Square is a string of the form x x ¯ , where x ¯ is a permutation of x . The Jumbled Square problem is the problem of finding for every location j in S , the longest jumbled square that ends in j , if such exists. We provide an algorithm that solves this problem in O ( | Σ | ( r 2 + n ) ) time, and O ( | Σ | n ) space. [ABSTRACT FROM AUTHOR]

In the classical pattern-matching problem, one is given a text and a pattern both of which are sequences of letters. The requirement is to find all occurrences of the pattern in the text. We studied two modifications of the classical problem, where each letter in the text and pattern is a set ( Set Intersection Matching problem) or a sequence ( Sequence Matching problem). Two “letters” are found to match if the intersection of the corresponding sets is not empty or if the two sequences have a common element in the same index. We first show that the two problems are similar by establishing a linear time reduction between them. We then show the first known non-trivial and efficient algorithms for these problems, when the maximum set/sequence size d is small. The first is a Monte Carlo randomized algorithm for Set Intersection Matching , that takes Θ ( 4 d n log ⁡ n log ⁡ m ) time, where n and m are the lengths of the text and the pattern, respectively; the failure probability is less than 1 n 2 . This algorithm can also be used, with slight modifications, when up to k mismatches is allowed. In addition, it can be used to maintain an approximation of factor 1 ± ϵ of the mismatch count in Θ ( 1 ϵ 2 4 d n log ⁡ n log ⁡ m ) time; the failure probability is bounded by 1 n . The second is a deterministic algorithm for Set Intersection Matching that can be used to count the number of matches at each index of the text in a total running time Θ ( ∑ i = 1 d ( σ i ) n log ⁡ m ) = O ( σ d n log ⁡ m ) , where σ is the size of the alphabet. The third algorithm, also deterministic, solves the Sequence Matching problem in Θ ( 4 d n log ⁡ m ) time. [ABSTRACT FROM AUTHOR]

In the Property Indexing Problem the goal is to preprocess a text T of size n over a constant sized alphabet Σ and a set of intervals π over the text positions, such that given a query pattern P of size m we can report all of the occurrences of P in T which are completely contained within some interval from π . This type of matching is extremely helpful for scenarios in molecular biology where it has long been a practice to consider special areas in the genome by their structure. It is also helpful for solving pattern matching problems over weighted sequences. So far the focus has been on the static version of this problem where the intervals are given a priori and never changed. This paper focuses on several dynamic settings of π including an incremental version where new intervals are inserted into π , a decremental version where intervals are deleted from π , a fully dynamic version where intervals may be inserted into or deleted from π , and a batched insertions version where sets of intervals are inserted into π . In particular, the batched version provides a new (optimal) algorithm for the static case. [ABSTRACT FROM AUTHOR]

We consider a generalization of the recently introduced order-preserving pattern matching. The difference between the standard pattern matching and the order-preserving variant is that instead of looking for an exact copy of the pattern, we only require that the relative order between the elements is the same. In our generalization, we additionally allow up to k mismatches between the pattern of length m and the text of length n , and the goal is to construct an efficient algorithm for small values of k . Our solution detects an order-preserving occurrence with up to k mismatches in O ( n ( log ⁡ log ⁡ m + k log ⁡ log ⁡ k ) ) time. [ABSTRACT FROM AUTHOR]

Scaled matching and permutation matching are two well known paradigms in the domain of pattern matching. Scaled matching refers to finding an occurrence of a pattern which is enlarged proportionally by some scale k within a larger text. Permutation matching is the problem of finding all substrings within a text where the character statistics of the substring and the pattern are the same. Permutation matching is easy, while scaled matching requires innovative solutions. One interesting setting of applications is the merge of the two. The problem of scaled permuted matching (i.e. first permuting and then scaling) has been addressed and solved optimally. However, it was left as an open problem whether there are efficient algorithms for permuted scaled matching. In this paper we solve the problem efficiently in a deterministic setting and optimally in a randomized setting. [ABSTRACT FROM AUTHOR]

Given a matrix of size N , two dimensional range minimum queries (2D-RMQs) ask for the position of the minimum element in a rectangular range within the matrix. We study trade-offs between the query time and the additional space used by indexing data structures that support 2D-RMQs. Using a novel technique—the discrepancy properties of Fibonacci lattices—we give an indexing data structure for 2D-RMQs that uses O ( N / c ) bits additional space with O ( c log ⁡ c ( log ⁡ log ⁡ c ) 2 ) query time, for any parameter c , 4 ≤ c ≤ N . Also, when the entries of the input matrix are from { 0 , 1 } , we show that the query time can be improved to O ( c log ⁡ c ) with the same space usage. [ABSTRACT FROM AUTHOR]

Suffix trees are highly regarded data structures for text indexing and string algorithms [MCreight 76, Weiner 73]. For any given string w of length n = | w | , a suffix tree for w takes O ( n ) nodes and links. It is often presented as a compacted version of a suffix trie for w , where the latter is the trie (or digital search tree) built on the suffixes of w . Here the compaction process replaces each maximal chain of unary nodes with a single arc. For this, the suffix tree requires that the labels of its arcs are substrings encoded as pointers to w (or equivalent information). On the contrary, the arcs of the suffix trie are labeled by single symbols but there can be Θ ( n 2 ) nodes and links for suffix tries in the worst case because of their unary nodes. It is an interesting question if the suffix trie can be stored using O ( n ) nodes. We present the linear-size suffix trie , which guarantees O ( n ) nodes. We use a new technique for reducing the number of unary nodes to O ( n ) , that stems from some results on antidictionaries. For instance, by using the linear-size suffix trie, we are able to check whether a pattern p of length m = | p | occurs in w in O ( m log ⁡ | Σ | ) time and we can find the longest common substring of two strings w 1 and w 2 in O ( ( | w 1 | + | w 2 | ) log ⁡ | Σ | ) time for an alphabet Σ. [ABSTRACT FROM AUTHOR]

Kubica et al. [33] and Kim et al. [29] introduced order-preserving pattern matching: for a given text the goal is to find its factors having the same ‘shape’ as a given pattern. Known results include a linear-time algorithm for this problem (in case of polynomially-bounded alphabet) and a generalization to multiple patterns. We propose an index that enables order-preserving pattern matching queries in time proportional to pattern length. The index can be constructed in O ( n log ⁡ log ⁡ n ) expected time or in O ( n log 2 ⁡ log ⁡ n / log ⁡ log ⁡ log ⁡ n ) worst-case time. It is an incomplete order-preserving suffix tree which may miss a single edge label at each branching node. For most applications such incomplete suffix trees provide the same functional power as the complete ones. We show a number of their applications, including computation of longest common factors, longest previously occurring factors and squares in a string in the order-preserving setting. We also give an O ( n log ⁡ n ) -time algorithm constructing complete order-preserving suffix trees. [ABSTRACT FROM AUTHOR]

We study the problem of indexing a text T [ 1 … n ] such that whenever a pattern P [ 1 … p ] and an interval [ α , β ] come as a query, we can report all pairs ( i , j ) of consecutive occurrences of P in T with α ≤ j − i ≤ β . We present an O ( n log ⁡ n ) space data structure with optimal O ( p + k ) query time, where k is the output size. [ABSTRACT FROM AUTHOR]

We study strategies of approximate pattern matching that exploit bidirectional text indexes, extending and generalizing ideas of [9] . We introduce a formalism, called search schemes, to specify search strategies of this type, then develop a probabilistic measure for the efficiency of a search scheme, prove several combinatorial results on efficient search schemes, and finally, provide experimental computations supporting the superiority of our strategies. [ABSTRACT FROM AUTHOR]

In this paper we define a new similarity measure: LCSk, aiming at finding the maximal number of k length substrings matching in both input strings while preserving their order of appearance, for which the traditional LCS is a special case, where k = 1 . We examine this generalization in both theory and practice. We first describe its basic solution and give an experimental evidence in real data for its ability to differentiate between sequences that are considered similar according to the LCS measure. We then examine extensions of the LCSk definition to LCS in at least k -length substrings ( LCS ≥ k ) and 2-dimensional LCSk and also define complementary EDk and ED ≥ k distances. [ABSTRACT FROM AUTHOR]

A growing number of measures of sequence similarity are being based on some underlying notion of relative compressibility. Within this paradigm, similar sequences are expected to share a large number of common substrings, or subsequences, or more complex patterns or motifs , and so on. In this paper, measures of sequence similarity are introduced and studied in which patterns in a pair are considered similar if they coincide up to a preset number of mismatches, that is, within a bounded Hamming distance. It is shown here that for some such measures bounds are achievable that are slightly better than O ( n 2 ) . Preliminary experiments demonstrate the potential applicability to phylogeny and classification of these similarity measures. [ABSTRACT FROM AUTHOR]

Pattern matching between traditional strings is well-defined for both uncompressed and compressed sequences. Prior to this work, parameterized pattern matching (p-matching) was defined predominately by the matching between uncompressed parameterized strings (p-strings) from the constant alphabet Σ and the parameter alphabet Π. In this work, we define the compressed parameterized pattern matching (compressed p-matching) problem to find all of the p-matches between a pattern P and text T , using only P and the compressed text T c . Initially, we present parameterized compression (p-compression) as a new way to losslessly compress data. Experimentally, we show that p-compression is competitive with various other standard compression schemes. Subsequently, we provide the compression and decompression algorithms. Next, two different approaches are developed to address the compressed p-matching problem: (1) using the recently proposed parameterized arithmetic codes ( pAC ) and (2) using the parameterized border array ( p - border ). Our general solution is independent of the underlying compression scheme. The results are further examined for catenate, Tunstall codes, Huffman codes, and LZSS. [ABSTRACT FROM AUTHOR]

We propose efficient methods to address key pattern matching problems in RNA secondary structures using the notion of structural strings. A structural string (s-string) is composed of constant symbols and parameter symbols from the alphabets Σ and Π, respectively. An individual symbol in the Π alphabet may be considered a complement of another unique symbol in Π. The notion of matching constants, parameters, and complements is referred to as the structural matching (s-match) problem, which is helpful in matching RNA and previously, was solved by the structural suffix tree ( sST ). Other approaches to RNA matching that do not openly consider the s-match include the use of affix data structures. In this paper, we provide new data structures and algorithms to address the s-match problem. Specifically, we introduce the structural suffix array and structural longest common prefix array and then identify how to s-match with these data structures. Our new s-matching solution is then used as the framework to answer various combinatorial queries encountered in matching RNA secondary structures. [ABSTRACT FROM AUTHOR]

Let D = { d 1 , d 2 , … , d D } be a collection of D string documents of n characters in total. The two-pattern matching problems ask to index D for answering the following queries efficiently. • Report/count the unique documents containing P 1 and P 2 . • Report/count the unique documents containing P 1 , but not P 2 . Here P 1 and P 2 represent input patterns of length p 1 and p 2 respectively. Linear space data structures with O ( p 1 + p 2 + n k log O ( 1 ) ⁡ n ) query cost are already known for the reporting version, where k represents the output size. For the counting version (i.e., report the value k ), a simple linear-space index with O ( p 1 + p 2 + n ) query cost can be constructed in O ( n 3 / 2 ) time. However, it is still not known if these are the best possible bounds for these problems. In this paper, we show a strong connection between these string indexing problems and the boolean matrix multiplication problem. Based on this, we argue that these results cannot be improved significantly using purely combinatorial techniques. We also provide an improved upper bound for a related problem known as common colors query problem . [ABSTRACT FROM AUTHOR]

We address a variant of the dictionary matching problem where the dictionary is represented by a straight line program (SLP). For a given SLP-compressed dictionary D of size n and height h representing m patterns of total length N , we present an O ( n 2 log ⁡ N ) -size representation of Aho–Corasick automaton which recognizes all occurrences of the patterns in D in amortized O ( h + m ) running time per character. We also propose an algorithm to construct this compressed Aho–Corasick automaton in O ( n 3 log ⁡ n log ⁡ N ) time and O ( n 2 log ⁡ N ) space. In a spacial case where D represents only a single pattern, we present an O ( n log ⁡ N ) -size representation of the Morris–Pratt automaton which permits us to find all occurrences of the pattern in amortized O ( h ) running time per character, and we show how to construct this representation in O ( n 3 log ⁡ n log ⁡ N ) time with O ( n 2 log ⁡ N ) working space. [ABSTRACT FROM AUTHOR]