-
Article
Open AccessOn the Practical Power of Automata in Pattern Matching
Many papers in the intersection of theoretical and applied algorithms show that the simple, asymptotically less efficient algorithm, performs better than the bestcomplex theoretical algorithms on random data o...
-
Chapter and Conference Paper
On Suffix Tree Detection
A suffix tree is a fundamental data structure for string processing and information retrieval, however, its structure is still not well understood. The suffix trees reverse engineering problem, which its research...
-
Article
Double String Tandem Repeats
A tandem repeat is an occurrence of two adjacent identical substrings. In this paper, we introduce the notion of a double string, which consists of two parallel strings, and we study the problem of locating all t...
-
Article
Multidimensional Period Recovery
Multidimensional data are widely used in real-life applications. Intel’s new brand of SSDs, called 3D XPoint, is an example of three-dimensional data. Motivated by a structural analysis of multidimensional dat...
-
Chapter and Conference Paper
Reconstructing Parameterized Strings from Parameterized Suffix and LCP Arrays
Reconstructing input from a data structure entails determining whether an instance of the data structure is in fact valid or not, and if valid, discovering the underlying data that it represents. In this paper...
-
Article
Open AccessDynamic and Internal Longest Common Substring
Given two strings S and T, each of length at most n, the longest common substring (LCS) problem is to find a longest substring common to S and T. This is a classical problem in computer science with an $$\mathca...
-
Chapter and Conference Paper
Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction
We study the query complexity of exactly reconstructing a string from adaptive queries, such as substring, subsequence, and jumbled-index queries. Such problems have applications, e.g., in computational biolog...
-
Chapter and Conference Paper
Approximating the Anticover of a String
The k-anticover of a string S is a set of distinct k-length substrings such that every index in S is contained in one of these substrings. The existence of an anticover indicates a lack of structure in S. It was ...
-
Chapter and Conference Paper
Multidimensional Period Recovery
Multidimensional data are widely used in real-life applications. Intel’s new brand of SSDs, called 3D XPoint, is an example of three-dimensional data. Motivated by a structural analysis of multidimensional dat...
-
Article
Can We Recover the Cover?
Data analysis typically involves error recovery and detection of regularities as two different key tasks. In this paper we show that there are data types for which these two tasks can be powerfully combined. A co...
-
Article
Mind the Gap!
We examine the complexity of the online Dictionary Matching with One Gap Problem (DMOG) which is the following. Preprocess a dictionary D of d patterns, where each pattern contains a special gap symbol that can m...
-
Chapter and Conference Paper
Finding Periods in Cartesian Tree Matching
In Cartesian tree matching, two strings match if the Cartesian trees of the strings are the same. In this paper we define full, initial, and general periods in Cartesian tree matching, and present an O(n) time al...
-
Chapter and Conference Paper
Searching for a Modified Pattern in a Changing Text
Much attention has been devoted recently to the dynamic model of pattern matching. In this model the input is updated or changed locally. One is interested in obtaining the appropriate search result in time th...
-
Article
On Representations of Ternary Order Relations in Numeric Strings
Order-preserving matching is a string matching problem of two numeric strings where the relative orders of consecutive substrings are matched instead of the characters themselves. The order relation between tw...
-
Chapter and Conference Paper
Longest Common Factor After One Edit Operation
It is well known that the longest common factor (LCF) of two strings over an integer alphabet can be computed in time linear in the total length of the two strings. Our aim here is to present an algorithm that...
-
Article
Configurations and Minority in the String Consensus Problem
The Closest String Problem is defined as follows. Let \(S\) S ...
-
Reference Work Entry In depth
Two-Dimensional Scaled Pattern Matching
-
Reference Work Entry In depth
Similarity Between Compressed Strings
-
Reference Work Entry In depth
Multidimensional Compressed Pattern Matching
-
Chapter and Conference Paper
Period Recovery over the Hamming and Edit Distances
A string S of length n has period P of length p if \(S[i]=S[i+p]\) ...