![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
Chapter and Conference Paper
Efficient randomized dictionary matching algorithms
The standard string matching problem involves finding all occurrences of a single pattern in a single text. While this approach works well in many application areas, there are some domains in which it is more ...
-
Chapter and Conference Paper
Alphabet independent and dictionary 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 matchin...
-
Chapter and Conference Paper
Efficient special cases of pattern matching with swaps
Let a text string of n symbols and a pattern string P of m symbols from alphabet Σ be given. A swapped version T′ of T is a length n string derived from T by a series of local swaps, (i.e. t ℓ ...
-
Chapter and Conference Paper
Faster Two Dimensional Pattern Matching with Rotations
The most efficient currently known algorithms for two dimensional matching with rotation have a worst case time complexity of O(n 2 m 3), where the s...
-
Chapter and Conference Paper
Approximate Matching in the L 1 Metric
Approximate matching is one of the fundamental problems in pattern matching, and a ubiquitous problem in real applications. The Hamming distance is a simple and well studied example of appro...
-
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...
-
Chapter and Conference Paper
Property Matching and Weighted Matching
Pattern Matching with Properties (Property Matching, for short), involves a string matching between the pattern and the text, and the requirement that the text part satisfies some property.
-
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
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
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
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 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
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
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 ...