58 Result(s)
within
Amihood Amir
Algorithm Analysis and Problem Complexity
-
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...
-
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...
-
Article
Configurations and Minority in the String Consensus Problem
The Closest String Problem is defined as follows. Let \(S\) S ...
-
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]\) ...
-
Chapter and Conference Paper
Range LCP Queries Revisited
The Range LCP problem is to preprocess a string \(S[1\dots n]\) , to enable efficient solutions of the following query: given a ...
-
Chapter and Conference Paper
On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling
Vertex Relabeling is a variant of the graph relabeling problem. In this problem, the input is a graph and two vertex labelings, and the question is to determine how close are the labelings. The distance measur...
-
Chapter and Conference Paper
Multiply Balanced k −Partitioning
The problem of partitioning an edge-capacitated graph on n vertices into k balanced parts has been amply researched. Motivated by applications such as load balancing in distributed systems and market segmentation...
-
Chapter and Conference Paper
Dictionary Matching with One Gap
The dictionary matching with gaps problem is to preprocess a dictionary D of d gapped patterns P 1,…,P d over alphabet Σ, where each gapped pattern P ...
-
Chapter and Conference Paper
Algorithms for Jumbled Indexing, Jumbled Border and Jumbled Square on Run-Length Encoded Strings
Jumbled Indexing, the problem of indexing a text for histogram queries, has been of much interest lately. In this paper we consider jumbled indexing for run-length encoded texts. We refute a form...
-
Chapter and Conference Paper
On the Efficiency of the Hamming C-Centerstring Problems
The Consensus String Problem is that of finding a string, such that the maximum Hamming distance from it to a given set of strings of the same length is minimized. However, a generalization is necessary for clust...
-
Chapter and Conference Paper
Approximate On-line Palindrome Recognition, and Applications
Palindrome recognition is a classic problem in computer science. It is an example of a language that can not be recognized by a deterministic finite automaton and is often brought as an example of a problem wh...
-
Chapter and Conference Paper
On Hardness of Jumbled Indexing
Jumbled indexing is the problem of indexing a text T for queries that ask whether there is a substring of T matching a pattern represented as a Parikh vector, i.e., the vector of frequency counts for each charact...
-
Chapter and Conference Paper
Pattern Matching with Non Overlap** Reversals - Approximation and On-line Algorithms
The Sorting by Reversals Problem is known to be \(\cal{NP}\) -hard. A simplification, Sorting by Signed Reversals is pol...
-
Chapter and Conference Paper
Detecting Approximate Periodic Patterns
Given ε ∈ [0, 1), the ε-Relative Error Periodic Pattern Problem (REPP) is the following:
