![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
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
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
Approximate Period Detection and Correction
Periodicity has been historically well studied and has numerous applications. In nature, however, few cyclic phenomena have an exact period.
-
Chapter and Conference Paper
Configurations and Minority in the String Consensus Problem
The Closest String Problem is defined as follows. Let S be a set of k strings {s 1,…s k }, each of length ℓ, find a string
-
Chapter and Conference Paper
Approximations and Partial Solutions for the Consensus Sequence Problem
The problem of finding the consensus of a given set of strings is formally defined as follows: given a set of strings S = {s 1,…s k }, and ...
-
Chapter and Conference Paper
Weighted Shortest Common Supersequence
The Shortest Common Supersequence (SCS) is the problem of seeking a shortest possible sequence that contains each of the input sequences as a subsequence. In this paper we consider applying the problem to Positio...
-
Chapter and Conference Paper
A PTAS for the Square Tiling Problem
The Square Tiling Problem was recently introduced as equivalent to the problem of reconstructing an image from patches and a possible general-purpose indexing tool. Unfortunately, the Square Tiling Problem was...
-
Chapter and Conference Paper
Approximate String Matching with Stuck Address Bits
A string S ∈ Σ m can be viewed as a set of pairs $\{ (s_i , i) \mid s_i\in S,\ i\in \{ 0,\ldots, m-...
-
Chapter
String Rearrangement Metrics: A Survey
A basic assumption in traditional pattern matching is that the order of the elements in the given input strings is correct, while the description of the content, i.e. the description of the elements, may be er...
-
Chapter and Conference Paper
Quasi-distinct Parsing and Optimal Compression Methods
In this paper, the optimality proof of Lempel-Ziv coding is re-studied, and a much more general compression optimality theorem is derived. In particular, the property of quasi-distinct parsing is defined. This pr...
-
Chapter and Conference Paper
Approximate String Matching with Address Bit Errors
A string S ∈ Σ m can be viewed as a set of pairs S = { (σ i , i) : i ∈ { 0,..., m − 1} }. We consider approx...
-
Chapter and Conference Paper
Two-Dimensional Range Minimum Queries
We consider the two-dimensional Range Minimum Query problem: for a static (m ×n)-matrix of size N = mn which may be preprocessed, answer on-line queries of the form “where is the position of a minimum element in ...
-
Chapter and Conference Paper
Deterministic Length Reduction: Fast Convolution in Sparse Data and Applications
In this paper a deterministic algorithm for the length reduction problem is presented. This algorithm enables a new tool for performing fast convolution in sparse data. The proposed algorithm performs the conv...
-
Chapter and Conference Paper
Asynchronous Pattern Matching
This paper introduces a new pattern matching model that has been gaining importance recently, that of Asynchronous Pattern Matching. Traditional pattern matching has assumed the possibility of errors in the data
-
Chapter and Conference Paper
Faster Two Dimensional Scaled Matching
The rapidly growing need for analysis of digitized images in multimedia systems has lead to a variety of interesting problems in multidimensional pattern matching. One of the problems is that of scaled matching, ...
-
Chapter and Conference Paper
Approximate Matching in Weighted Sequences
Weighted sequences have been recently introduced as a tool to handle a set of sequences that are not identical but have many local similarities. The weighted sequence is a “statistical image” of this set, wher...