arXiv:1607.05626v2 [cs.DS] 11 Nov 2016

Streaming k-mismatch with error correcting and applications
Jakub Radoszewski1 and Tatiana Starikovskaya2
1

2

University of Warsaw
Université Paris-Diderot

Abstract
We present a new streaming algorithm for the k-Mismatch problem, one of the most basic problems in pattern matching. Given a
pattern and a text, the task is to find all substrings of the text that are
at the Hamming distance at most k from the pattern. Our algorithm
is enhanced with an important new feature called Error Correcting, and its complexities for k = 1 and for a general k match those
of the best known solutions for the k-Mismatch problem from FOCS
2009 and SODA 2016. As a corollary we develop a series of streaming algorithms for pattern matching on weighted strings, which are
a commonly used representation of uncertain sequences in molecular
biology.

1

Introduction

In this work we design efficient streaming algorithms for a number of problems of approximate pattern matching. In this class of problems we are
given a pattern and a text and wish to find all substrings of the text that
are “similar” to the pattern. We assume that the text arrives as a stream,
one symbol at a time.
The first small-space streaming algorithms for pattern matching were
suggested in the pioneering paper by Porat and Porat in FOCS 2009 [18]. In
particular, they showed an algorithm for the Pattern Matching problem,
where one must find all exact occurrences of the pattern in the text. For a
pattern of length m their algorithm takes only O(log m) space and O(log m)
time per each symbol of the text, and reports all exact occurrences of the
pattern in the text as they occur. In 2010, Ergun et al. presented a slightly
simpler version of the algorithm [13], and finally in 2011 the running time
of the algorithm was improved to constant [6]. The next logical step was

to study the complexity of approximate pattern matching in the streaming
model in which we are to find all substrings of the text that are at a small
distance from the pattern. The most popular distances are the Hamming
distance, L1 , L2 , L∞ -distances, and the edit distance. Unfortunately, the
general task of computing these distances for each alignment of the pattern
and of the text precisely requires at least Ω(m) space. This lower bound
holds even for randomised algorithms [10].
However, this is not the case if we allow approximation or if it is sufficient to compute the exact distances only when they are small. Here
we focus on approximate pattern matching under the Hamming distance.
In the k-Mismatch problem we are given a pattern and a text, and we
must find all substrings of the text that are at the Hamming distance
at most k from the pattern. Let m be the length of the pattern and n
be the length of the text. If we are interested in computing a (1 + ε)approximation of the Hamming distance for all alignments of the pattern
√
and of the text, then this can be done in O(ε−5 m log4 m) space and
O(ε−4 log3 m) time per arriving symbol [11]. And if we are only interested
in computing the Hamming distances at the alignments where they do not
exceed a given threshold k (the k-Mismatch problem), then Porat and Porat [18] showed a randomised streaming algorithm that solves this problem
in O(k3 log7 m/ log log m) space and O(k2 log5 m/ log log m) time per arriving symbol; they also presented an algorithm for a special case of k = 1
with O(log4 m/ log log m) space and O(log3 m/ log log m) time per arriving
symbol. Recently, their result was improved (in
√ terms of the dependency
on k) to O(k2 log11 m/ log log m) space and O( k log k + log5 m) time per
arriving symbol by Clifford et al. [8].
Our first contribution is a new streaming algorithm for the k-Mismatch
problem. The crucial feature of our algorithm is that, for each alignment
where the Hamming distance is at most k, it can also output the differences
of symbols of the pattern and of the text in the mismatching positions. This
is particularly surprising as we are not allowed to store a copy of the pattern
or of the text in the streaming setting. The k-Mismatch problem extended
with computing this additional characteristic is called here the k-Mismatch
with Error Correcting problem. We first develop a solution for k = 1.
Theorem 1.1. The 1-Mismatch with Error Correcting problem can
be solved in O(log5 m/ log log m) space and O(log5 m/ log log m) time per
arrival. The probability of error is at most 1/poly(n).
As a corollary we obtain a k-Mismatch with Error Correcting

2

algorithm for arbitrary k via an existing randomised reduction to the 1Mismatch with Error Correcting problem [18, 8].
Theorem 1.2. The k-Mismatch with Error Correcting problem can
be solved in O(k2 log10 m/ log log m) space and O(k log8 m/ log log m) time
per arrival. The probability of error is at most 1/poly(m).
Since in the k-Mismatch with Error Correcting problem we need
at least Ω(k) time per arrival to list the symbol differences, the dependency
of the running time of our algorithm on k is optimal. The time complexity of
our k-Mismatch with Error Correcting algorithm is better than the
time complexity of the k-Mismatch algorithm of [18] and worse than that
of [8]. Our algorithm also uses less space than the k-Mismatch algorithm
of [18] (in terms of k) and the k-Mismatch algorithm of [8]. For the former,
it is explained by the fact that we use a more efficient reduction. For the
latter, it is because we do not need the elaborated time-saving techniques
of Clifford et al. [8] (as the running time of our algorithm is already almost
optimal). We note that a similar problem was considered previously in [19]
by Porat and Lipsky. They introduced a small-space representation of a
stream called a “sketch” that can be efficiently maintained under a symbol
change and can be used to compute the Hamming distance between two
streams as well as to correct the errors between them. Unfortunately, it is
not clear whether their sketches can be efficiently maintained over a sliding
window (i.e. for substrings of the text) and therefore we cannot use them in
our model.
The Error Correcting feature is a very powerful tool. We demonstrate this by developing the first streaming algorithms for the problem of
pattern matching on weighted strings. A weighted string (also known as
weighted sequence, position probability matrix or position weight matrix,
PWM) is a sequence of probability distributions on the alphabet. Weighted
strings are a commonly used representation of uncertain sequences in molecular biology. In particular, they are used to model motifs and have become
an important part of many software tools for computational motif discovery,
see e.g. [20, 21]. In the Weighted Pattern Matching problem we are
given a text and a pattern, both of which can be either weighted or regular
strings. If either only the text or only the pattern are weighted, the task is
to find all alignments of the text and of the pattern where they match with
probability above a given threshold 1/z. In the most general case, when
both the pattern and the text are weighted, we must find all alignments of
the text and of the pattern where there exists a regular string that matches
both the text and the pattern with probability at least 1/z.
3

As it was already mentioned, we are the first to consider the Weighted
Pattern Matching problem in the streaming setting. In the offline setting
the most commonly studied variant, when the text is a weighted string of
length n and the pattern is a regular string, can be solved in O(n log n) time
via the Fast Fourier Transform [7] or in O(n log z) time using the suffix array
and lookahead scoring [16]. This variant has been also considered in the
indexing setting, in which we are to preprocess a weighted text to be able to
answer queries for multiple patterns; see [1, 14, 5, 3]. The symmetric variant
of the Weighted Pattern Matching problem, when only the pattern is
weighted, is closely related to the problem of profile matching [17] and admits
O(n log n)-time and O(n log z)-time solutions as well. Finally, the variant
when both the text and the pattern are weighted was introduced in [4],
where an O(nz 2 log z)-time solution was presented. Later a more efficient
√
O(n z log log z)-time solution was devised in [16]. The offline algorithms
use Ω(m) space and the best indexing solution uses Ω(nz) space. There has
been also considered a problem of computing Hamming and edit distances
for weighted strings [2].
We consider each of the three variants of the Weighted Pattern
Matching problem. We assume z < m and for each variant demonstrate two algorithms. The algorithms use different methods to find the
alignments where the pattern and the text might match with probability at least 1/z. The second method gives better space complexity for
log10 m ≤ z < m. Note that this setting is not uncommon, because even
choosing a letter with probability 0.9 at log m positions gives match probability 1/mc for a constant c > 0. Let Slog z = O(log2 z · log10 m/ log log m)
and Tlog z = O(log z · log8 m/ log log m) be the space and the time complexities for the k-Mismatch with Error Correcting for k = log z and a
pattern of length m (See Theorem 1.2). We first consider the variant when
only the pattern is weighted.
Theorem 1.3. If only the pattern is weighted, the Weighted Pattern
Matching problem can be solved in O(z log m) space and O(log log(z + m))
time per arrival with error probability 1/poly(n) or in O(z) + Slog z space
and Tlog z time with error probability 1/poly(m).
For the case when the pattern is a regular string and the text is weighted,
we show a (1 − ε)-approximation streaming algorithm. At each alignment
the algorithm outputs either “Yes” or “No”. If the pattern matches the
fragment of the text, the algorithm outputs “Yes”. If the match probability
is between (1 − ε)/z and 1/z, it can output either “Yes” or “No”, and
4

otherwise it outputs “No”. If it outputs “Yes”, it also outputs a (1 − ε)approximation of the match probability between P and T .
Theorem 1.4. If only the text is weighted, there is a (1 − ε)-approximation
streaming algorithm that solves the Weighted Pattern Matching problem in O(z log1/(1−ε) z + z log m) space and O(z log z) time per arrival with
error probability 1/poly(n) or in O(z log1/(1−ε) z)+Slog z space and O(z log z)+
Tlog z time with error probability 1/poly(m).
Our final result is a (1 − ε)-approximation streaming algorithm for the
most general case when both the pattern and the text are weighted. At
each alignment the algorithm outputs either “Yes” or “No”. If there is a
regular string that matches the text and the pattern at this alignment with
probability above 1/z, the algorithm outputs “Yes”. It may also output
“Yes” if there is a string that matches with probability between (1 − ε)/z
and 1/z. Otherwise it outputs “No”.
Theorem 1.5. If both the text and the pattern are weighted, there is a (1−ε)approximation streaming algorithm that solves the Weighted Pattern
Matching problem in O(z log1/(1−ε) z + z 2 log m) space and O(z log z +
z log log(z + m)) time per arrival with error probability 1/poly(n) or in
O(z log1/(1−ε) z) + z · Slog z space and O(z log z) + z · Tlog z time per arrival
with error probability 1/poly(m).
Model of computation. We account for all the space we use, and cannot
afford to store a copy of the text or of the pattern. We assume that we
receive the pattern first and can preprocess it by reading it in a streaming
fashion several times. After having preprocessed the pattern we receive the
text that arrives as a stream, one symbol at a time. The indicated error
probabilities are per arrival. We assume a constant-sized alphabet Σ. A
symbol of a weighted string is a vector of probabilities of the letters in which
dw
all entries are of the form cp/2 , where w is the machine word size, c and d
are constants, and p is an integer that fits in a constant number of machine
words (log-probability model). Additionally, the probability 0 has a special
representation. The only operations on probabilities in our algorithms are
multiplications and divisions, which can be performed exactly in O(1) time
in this model.

5

2

Weighted Pattern Matching

In this section we present our solutions to the three variants of the Weighted
Pattern Matching problem. The solution to the k-Mismatch with Error Correcting problem is deferred until Section 3.

2.1

Proof of Theorem 1.3 — only pattern is weighted

We start by giving an algorithm that takes O(z log m) space and O(log log(z+
m)) time per arrival. At the preprocessing step we generate all (regular)
strings that match the pattern with probability at least 1/z. We do this in
a naive fashion by maintaining a set of regular strings that match the prefix
of the pattern received so far with probability at least 1/z. When a new
position of the pattern arrives, we try to extend each string in the set with
all possible letters and update the match probabilities. Note that the size
of the set never exceeds z, as the sum of the probabilities over all strings
in the set is at most 1. If a substring of the text T matches P , it must be
an occurrence of one of the generated strings. We find all such occurrences
using the streaming Dictionary Matching algorithm by Clifford et al. [9]
for the dictionary of the z generated strings. For a dictionary of z strings
of length m the algorithm takes O(z log m) space and O(log log(z + m))
time per symbol. The algorithm is randomised and has error probability
1/poly(n). This gives us the first algorithm of Theorem 1.3.
To explain the second algorithm, we define H (P ) to be a regular string
obtained from P by choosing at each position the symbol with the maximum
probability. At each alignment where P and T match with probability at
least 1/z, the number of mismatches between H (P ) and T is at most log z
(because at each mismatch the probability of P and T to match is at most
1/2). To find such alignments, we use our k-Mismatch algorithm for k =
log z. It remains to explain how we retrieve the match probabilities. We
only need to retrieve the match probabilities if they are ≥ 1/z, i.e. the mlength substring of the text must match exactly one of the at most z strings
generated in the first solution. Let M be the set of all different mismatches
between the generated strings and H (P ); each mismatch is specified by its
position i and a letter a 6= H (P ) [i]. We claim that |M | ≤ z. Indeed, from
each mismatch (i, a) from M one can produce a regular string that matches
P with probability ≥ 1/z by taking H (P ) and replacing H (P ) [i] by a, and
there are at most z such strings.
When reading the pattern, we compute a set M ′ ⊇ M of mismatches
(i, a) together with the values p(i, a) = Pr[P [i] = a]/Pr[P [i] = H (P ) [i]]. We
6

insert all pairs (i, a) for i = 1, . . . , m, a 6= H (P ) [i] into two balanced BSTs,
one indexed by p(i, a) and the other by (i, a). We keep the size of M ′ not
greater than z by removing the elements with the smallest p(i, a) if needed.
At the end, using the second balanced BST, we can retrieve the match
probability of the candidate occurrence and P in O(log2 z) = O(log z log m)
time (z < m). Thus we arrive at the conclusion of Theorem 1.3.

2.2

Proof of Theorem 1.4 — only text is weighted

In this section we show two solutions to the Weighted Pattern Matching problem for a regular pattern P and a weighted text T . We assume
that ε < 1/2. If ε > 1/2, we can use the 1/2-approximation algorithm that
has the same asymptotic complexity and better approximation factor. We
start by giving a definition of maximal matching suffixes of prefixes of the
text T that will play a crucial role in both algorithms.
Definition 2.1. A maximal matching suffix of T [1, q] is a (regular) string
S such that S matches T [q − |S| + 1, q] with probability ≥ 1/(2z) and either
|S| = q or any string aS, for a ∈ Σ, matches T [q − |S|, q] with probability
< 1/(2z).
The reason for selecting the cut-off value of 1/(2z) will become clear later
(in Lemma 2.2, where we need the cut-off to be at least (1 − ε)/z). The
number of maximal matching suffixes of T [1, q] never exceeds 2z [1]. Note
that P matches T at an alignment q with probability ≥ 1/z if and only if
there is a maximal matching suffix S of T [1, q] that ends with it. Moreover,
the match probability between P and T is equal to the match probability
between the m-length suffix of S and T .
We maintain each maximal matching suffix S and the probabilities xi
of a match between S and T [i] as a stream. Let H (T ) be a regular string
obtained from T by choosing at each position the symbol with the maximum
probability. We call a position i in the stream a mismatch position if the
corresponding letter in S is different than H (T ) [i]; note that we then have
xi ≤ Q
1/2. Let r be the rightmost mismatch position in the stream such
that i≥r+1 xi ≤ 1/(2z). If such mismatch position does not exist, we put
r = 0. Note that there are at most log z + 1 mismatch positions to the right
of r. We index the stream by these mismatch positions and the differences
between the letters of S and H (T ) in these positions. We also store the total
product of numbers located to the right of each of these at most log z + 1
mismatch positions.

7

Let Σq+1 be the set of letters b ∈ Σ such that Pr[T [q + 1] = b] ≥ 1/(2z).
At the arrival of position q + 1 we create |Σq+1 | copies of each stream. We
then add Pr[T [q + 1] = b] for each b ∈ Σq+1 to the b-th copy of each stream
and update the mismatch positions and all related information in O(log z)
time in a straightforward manner. At this moment the index r in some
streams might have increased and we might have more than one stream for
a single maximal matching suffix. On the other hand, the streams that
correspond to a fixed maximal matching suffix have the same indices. We
can therefore delete the duplicates as follows. The first step is to build a
trie (see [12] for a definition) on the indices of the streams in O(z log z) time
and space to sort the streams. The indices are inserted into the trie from
right to left. (Children in the trie are stored using perfect hashing.) The
second step is to select one stream for each index and delete the remaining
ones.
We now explain how we maintain an approximate value of the match
probability between the m-length suffix of S and T . To this end, we introduce the Sliding Window Product problem. In the Sliding Window
Product problem we are given a stream of numbers from [0, 1] arriving
one number at a time, an integer m, and a threshold 1/z, and must find the
product of numbers in each window of length m provided that it is above
the threshold. We give a (1 − ε)-approximation algorithm for this problem.
More precisely, when a new symbol arrives, the algorithm outputs either a
number or “No”. If it outputs a number, it is a (1 − ε)-approximation of
the product of the last m numbers, and otherwise the product is at most
(1 − ε)/z.
Lemma 2.2. For a stream of numbers {xi }∞
i=1 , where xi ∈ [0, 1], arriving
one at a time, and a window width m, there is a deterministic (1 − ε)approximation algorithm that takes O(log1/(1−ε) z) space and O(1) time per
arrival and solves the Sliding Window Product problem.
Proof.
At time q the

 algorithm maintains a family of at most M (z) =
2 log1−ε ((1 − ε)/z) intervals [i1 , i2 − 1], [i2 , i3 − 1], . . . , [ik(q) , q], such that
1 ≤ i1 < i2 < . . . < ik(q) < ik(q)+1 = q + 1, which obeys the following
invariant.
(i) All intervals [ij , ij+1 − 1] for j ≥ 2 are subintervals of [q − m + 1, q],
and [i1 , i2 − 1] has a non-empty intersection with [q − m + 1, q];
(ii) If xij < 1 − ε, then ij+1 = ij + 1;
8

(iii) Otherwise, xij · xij +1 · . . . · xij+1 −1 ≥ 1 − ε and either j = k(q) or
xij · xij +1 · . . . · xij+1 < 1 − ε.
The algorithm stores the product of numbers in each interval and the
total product of numbers in all intervals. When xq+1 arrives, it updates the
family in the following way. Let π be the product of numbers in the interval
[ik(q) , q]. If π · xq+1 ≥ 1 − ε, then the algorithm extends the interval [ik(q) , q]
by the element xq+1 . Otherwise, it creates a new interval [q + 1, q + 1]. If
the number of intervals becomes larger than M (z) or if i2 ≤ (q + 1) − m + 1,
the algorithm deletes the leftmost interval [i1 , i2 − 1]. Finally it updates
the total product of numbers in the intervals. Let us now explain how the
algorithm exploits the intervals.
Note that the product of numbers in each two consecutive intervals is at
most 1 − ε. Therefore, if q − m + 1 < i1 , then the product of the last m
numbers is at most (1 − ε)/z and the algorithm outputs “No”. Otherwise
from the invariant it follows that q − m + 1 ∈ [i1 , i2 − 1]. In this case we
output the total product of the numbers in the intervals. Recall that if
[i1 , i2 − 1] is not a singleton interval, then the product of numbers in it is
at least 1 − ε. Therefore, the answer will be a (1 − ε)-approximation of
xq−m+1 ·xq−m+2 · . . . · xq . The
 space complexity follows from the fact that
M (z) = 2 log1−ε ((1 − ε)/z) .
Finally, we explain how we find a maximal matching suffix that ends
with P . We will give two different methods resulting in the two algorithms
of Theorem 2.2. The first method is based on a straightforward application
of the streaming Pattern Matching algorithm [6]. This algorithm uses
O(log m) space and takes O(1) time to process a text symbol. In the first
method, we simply run the algorithm for the pattern P and each of the
maximal matching suffixes streams. The second method is based on our kMismatch algorithm. If P matches T at some alignment q with probability
at least 1/z, then H (T ) [q − m + 1, q] is a log z-mismatch occurrence of P
(see Section 2.1). We use our k-Mismatch algorithm with k = log z for P
and H (T ) to find all such alignments. When we identify a log z-mismatch
occurrence of P in H (T ), we find a stream that corresponds to a maximal
matching suffix that ends with P , if any (using the indexing trie). Suppose
we have found a maximal matching suffix S that ends with P using either
of the two methods. We then use the algorithm of Lemma 2.2 to compute
a (1 − ε)-approximation of the product of the last m probabilities in the
stream associated with S and output it as an answer.
Let us analyse the two algorithms. Since the number of maximal match9

ing suffixes never exceeds 2z, the total number of streams is O(z). Updating
the streams, including the duplicate removal, takes O(z log z) space and time
per position. For each of the streams we run the algorithm of Lemma 2.2,
which takes O(z log1/(1−ε) z) space and O(z) time per position. Therefore,
the first algorithm requires O(z log1/(1−ε) z + z log m) space and O(z log z)
time per position. The error probability of the Pattern Matching algorithm and, therefore, of our algorithm is 1/poly(n) per position. The second
algorithm can output an incorrect answer only when the k-Mismatch algorithm errs, which happens with probability 1/poly(m). For k = log z, the
k-Mismatch algorithm takes Slog z space and Tlog z time per arriving symbol.
Finally, to find the “right” stream we need just O(log z) additional time per
position. In total, this is O(z log1/(1−ε) z)+Slog z space and O(z log z)+Tlog z
time per position.

2.3

Proof of Theorem 1.5 — both the text and the pattern
are weighted

We conclude by showing a streaming algorithm for the Weighted Pattern
Matching problem when both the pattern and the text are weighted. Our
solution combines the ideas of the two previous sections. Recall that at each
alignment the algorithm must output “Yes” if there is a regular string that
matches the text and the pattern with probability above 1/z. The algorithm
may also output “Yes” if there is a string that matches with probability
between (1 − ε)/z and 1/z. Otherwise it outputs “No”.
For the pattern P we generate the at most z regular strings that match
it with probability ≥ 1/z. For the text T we maintain a set of at most
2z streams for the maximal matching suffixes in the text. For each of the
streams we run the algorithm of Lemma 2.2. There is a regular string that
matches the pattern and the text with probability ≥ 1/z if and only if the
following two conditions hold: (i) one of the maximal matching suffixes ends
with a string generated for the pattern and (ii) the product of the last m
probabilities in the suffix’s stream is at least 1/z. We can verify the second
condition using the approximation of Lemma 2.2 as in Section 2.2. To verify
the first condition, we again give two methods. The first method is to run
the Dictionary Matching algorithm for the strings generated for the
pattern and each of the maximal matching suffixes. The second method is
based on our k-Mismatch algorithm. If P matches T at some alignment q,
then H (T ) [q − m + 1, q] must be a log z-occurrence of one of the strings we
generated for the pattern. We use our k-Mismatch algorithm with k = log z
for each of the generated strings and H (T ) to find all such occurrences. At
10

each alignment q we consider log z-occurrences of the generated strings and
build a trie of their indices, where the indices are defined as in Section 2.2.
If a maximal matching suffix ends with one of these strings, its index must
be in the trie. We can check this condition is O(z log z) time in total.
Let us analyse the two algorithms. Updating the suffix streams takes
O(z log z) time as there are O(z) of them. For each of the streams we
run the algorithm of Lemma 2.2, which takes O(z log1/(1−ε) z) space and
O(z) time. Hence, the first method takes O(z log1/(1−ε) z + z 2 log m) space
and O(z log z + z log log(z + m)) time per position. The error probability is 1/poly(n). The second method can output an incorrect answer only
when one of the k-Mismatch algorithms errs, which happens with probability z/poly(m) = 1/poly(m). For k = log z the k-Mismatch algorithm
takes Slog z space and Tlog z time per symbol. Building the trie of mismatch encodings takes O(z log z) time. Searching for the indices in the trie
takes O(z log z) time. In total, this is O(z log1/(1−ε) z) + z · Slog z space and
O(z log z) + z · Tlog z time.

3

k-mismatch with error correcting

In this section we give our solution to the k-Mismatch problem for k = 1
(Theorem 1.1) and for a general value of k (Theorem 1.2).

3.1

Proof of Theorem 1.1: k = 1

Consider two m-length strings X and Y . In [18] Porat and Porat showed
that the Hamming distance between X and Y is equal to 1 if and only
if for each prime q ∈ [log m, 2 log m] there is exactly one j ≤ q such that
subsequences X[j]X[j + q]X[j + 2q] . . . and Y [j]Y [j + q]Y [j + 2q] . . . are
not equal. This observation formed the foundation of their 1-Mismatch
algorithm [18]. They also noticed that, by the Chinese remainder theorem,
the starting positions of the non-equal subsequences uniquely determine the
mismatch position between X and Y . However, their algorithm discards
all the information about the mismatching subsequences as soon as it discovers a mismatch and, therefore, cannot be augmented with the Error
Correcting feature. To overcome this difficulty, we introduce a notion of
1-mismatch sketches.
Let us start by recalling the definition of a rolling hash function called
Rabin-Karp fingerprint [15] and its properties. The Rabin-Karp
fingerprint
P
of a string X = X[1] . . . X[ℓ] is defined as φ(X) = ( ℓi=1 X[i] · r i ) mod p,
where p is a prime and r is a random integer in Fp . Importantly, if we
11

choose p to be large enough, then the collision probability of any two ℓlength strings X and Y , where ℓ ≤ m, will be at most 1/poly(m). We will
also need the following lemma which is a straightforward corollary of the
definition of Rabin-Karp fingerprints.
Lemma 3.1. Let X, Y be two strings, Z = XY be their concatenation, and
let ϕ(X), ϕ(Y ), and ϕ(Z) be the Rabin-Karp fingerprints of X, Y , and Z,
respectively. Then
ϕ(Z) = (ϕ(X) + r |X| · ϕ(Y )) mod p.
Therefore if we assume that together with a Rabin-Karp fingerpint of
a string of length ℓ we store r ℓ mod p and r −ℓ mod p, then knowing the
Rabin-Karp fingerprints of two of the strings X, Y , Z, one can compute the
Rabin-Karp fingerprint of the third string in O(1) time. We are now ready
to give the definition of 1-mismatch sketches.
Definition 3.2 (1-mismatch sketch). For a prime q, the 1-mismatch sketch
of a string X is a vector of length q, where the j-th element is the Rabin-Karp
fingerprint of the subsequence X[j]X[j + q]X[j + 2q] . . .
Lemma 3.3. Let X, Y be two strings, Z = XY be their concatenation.
Consider the 1-mismatch sketches of X, Y , and Z defined for a prime q.
Then:
(i) If X = Y , then their 1-mismatch sketches are equal;
(ii) Given the 1-mismatch sketches of X and Y , we can compute the 1mismatch sketch of Z in O(q) time;
(iii) Given the 1-mismatch sketches of X and Z, we can compute the 1mismatch sketch of Y in O(q) time;
(iv) Given the 1-mismatch sketch of X, we can compute the 1-mismatch
sketch of X α in O(q log α) time, where α is an integer and X α is a
concatenation of α copies of X.
Proof. Property (i) is a direct corollary of the definitions of Rabin-Karp
fingerprints and 1-mismatch sketches. As for Property (ii), note that we
need to compute the Rabin-Karp fingerprints of the at most q concatenations
of pairs of strings, similarly for Property (iii) we only need to compute the
Rabin-Karp fingerprints of the at most q strings constructed from Y given
the Rabin-Karp fingerprints of the at most q strings constructed from X and
their concatenations (in Z). Finally, Property (iv) follows from Property (ii)
as we can compute the 1-mismatch sketch of a square of any string given its
1-mismatch sketch in O(q) time.
12

Overview of the solution. We reduce the 1-Mismatch with Error
Correcting problem to O(log m) instances of a special case of this problem
where the mismatch is required to belong to the second half of the pattern.
More formally, consider ⌈log m⌉ + 1 partitions P = Pi Si , where Pi is a prefix
of length min{2i , m} and Si is the remaining suffix, for i = 0, 1, . . . , ⌈log m⌉.
We say that a substring of T is a right-half 1-mismatch occurrence of Pi if
either i = 0 and P0 does not match, or i ≥ 1 and the mismatch is at position
j > 2i−1 in Pi .
Observation 3.4. Any 1-mismatch occurrence of P in T is a right-half
1-mismatch occurrence of some Pi followed by an exact occurrence of Si .
We run two parallel processes for each i. The first process searches for
right-half 1-mismatch occurrences of Pi . After having found a right-half
1-mismatch occurrence, it passes the information about it (including its 1mismatch sketches) to the second process that decides if it is followed by
an exact occurrence of Si . Let us recall a streaming Pattern Matching
algorithm that lies in the foundation of both processes. For a pattern Q
and text T the algorithm takes O(log |Q|) space and O(log |Q|) per symbol. This algorithm is not the best known solution, but it gives the desired
time bounds and is conceptually simple. The algorithm stores O(log |Q|)
levels of positions of T . Positions in level j are occurrences of Q[1, 2j ] in
the suffix of the current text T of length 2j+1 . The algorithm stores the
Rabin-Karp fingerprints of T from the beginning of T up to each of these
positions. If there are at least 3 such positions at one level, then there is
a large overlap of the occurrences of Q[1, 2j ] and therefore all the positions
form a single arithmetic progression whose difference equals the length of
the minimal period of Q[1, 2j ]. This allows to store the aforementioned information very compactly, using only O(log |Q|) space in total. Finally, the
algorithm stores the Rabin-Karp fingerprint of the current text and of all
prefixes Q[1, 2j ]. When a new symbol T [q] arrives, the algorithm considers
the leftmost position ℓj in each level j. If q − ℓj + 1 is smaller than 2j+1 ,
the algorithm does nothing. Otherwise if the fingerprints imply that ℓj is
an occurrence of Q[1, 2j+1 ], the algorithm promotes it to the next level, and
if ℓj is not an occurrence of Q[1, 2j+1 ], the algorithm discards it. When a
position reaches the top level, it is an occurrence of Q and the algorithm
outputs it. For more details, see [18, 13, 6].
1-mismatch occurrences of Pi . Suppose a new symbol T [q] has arrived.
To check whether T [q−|Pi |+1, q] is a right-half 1-mismatch occurrence of Pi ,
13

we use the 1-Mismatch algorithm [18], which requires O(log4 m/ log log m)
space and O(log3 m/ log log m) time per symbol. This algorithm also returns
the mismatch position. However, the algorithm does not know neither the
difference of symbols at the mismatch position nor the 1-mismatch sketches
of the occurrence. To extend the algorithm with the required functionality,
we use the Pattern Matching algorithm for a pattern Q = Pi and T . If
T [q − |Pi | + 1, q] is a right-half 1-mismatch occurrence of Pi , then Pi [1, 2i−1 ]
matches at the position q − |Pi | + 1 exactly. It follows that at time q the
position q − |Pi | + 1 is stored at level i − 1 of the Pattern Matching
algorithm, and we know the Rabin-Karp fingerprints of T [1, q − |Pi |] and
T [1, q]. Therefore, we can compute the Rabin-Karp fingerprint of T [q −
|Pi | + 1, q] in O(1) time. Let j be the mismatch position and φ(Pi ) and
φ(T [q −|Pi |+1, q]) be the Rabin-Karp fingerprints of Pi and T [q −|Pi |+1, q],
respectively. We use the fingerprints to compute the difference of symbols
of Pi and T at the position j.
Lemma 3.5. Assume that X and Y are two strings of length m that differ
only at position j. Knowing the Rabin-Karp fingerprints of X and Y , one
can compute X[j] − Y [j] in O(log m) time.
Proof. Let φ(X) and φ(Y ) be the Rabin-Karp fingerprints of X and Y ,
respectively. Then X[j]−Y [j] is equal to (φ(X)−φ(Y ))·r −j (mod p), where
p and r are the integers used in the definition of Rabin-Karp fingerprints.
This formula can be evaluated in O(log m) time.
As a final step we compute the 1-mismatch sketches of T [q−|Pi |+1, q] and
send them to the second process. We assume that during the preprocessing
step the algorithm precomputes the 1-mismatch sketches of Pi for all primes
in [log m, 2 log m], which requires O(log2 m/ log log m) space. It can then
restore the 1-mismatch sketches of T [q − |Pi | + 1, q] in O(log2 m/ log log m)
time by fixing the symbol in the mismatch position.
Exact occurrences of Si . We now describe the second process built on
top of the Pattern Matching algorithm for the pattern Q = Si and T .
Since for each new position q the first process tells whether it is preceded
by a right-half 1-mismatch occurrence of Pi , all we need is to carry this
information from the level 0 of the Pattern Matching algorithm to the
top level. We claim that it suffices to store the 1-mismatch sketches for a
constant number of positions in each level. Using them, we will be able to
infer the remaining unstored information.

14

Consider level j. The progression that the algorithm currently stores for
this level can be a part of a longer progression of occurrences of Si [1, 2j ] in
T . Let ℓ be some occurrence of Si [1, 2j ] for which we would like to figure
out whether it is preceded by a right-half 1-mismatch occurrence of Pi . If
ℓ is far from the start of the long progression, then the text preceding ℓ is
periodic with period ρj being the shortest period of Si [1, 2j ], and we can use
this fact to infer the 1-mismatch information. So our main concern is the
positions ℓ that are at the distance of at most |Pi | = 2i from the start of
the long progression. We define four positions ℓaj , a = 1, 2, 3, 4, that help us
to restore the information in this case. Note that we can easily determine
the moment when a new long progression starts, as this is precisely the
moment when the difference between two consecutive positions in level j
becomes larger than ρj . We define ℓ1j as the first position preceded by a
right-half 1-mismatch occurrence of Pi that was added to level j since that
moment. We further define ℓaj as the leftmost terms preceded by a right-half
1-mismatch occurrence of Pi in [ℓ1j + (a − 1) · 2i−2 , ℓ1j + a · 2i−2 ] for a = 2, 3, 4.
(If such terms exist; otherwise they are left undefined). The algorithm stores
the 1-mismatch sketches of T [1, ℓaj − 2i − 1] for each a = 1, 2, 3, 4 and the
1-mismatch sketches of T [1, ℓ1j − 1].
Besides, the algorithm stores a number of 1-mismatch sketches for the
pattern, which are computed during the preprocessing step and occupy
O(log3 m/ log log m) space in total. First, it stores the 1-mismatch sketches
of the minimal period of Pi [1, 2i−1 ]. Second, the algorithm stores the 1mismatch sketches of the minimal period Si [1, ρj ] of Si [1, 2j ] for each j =
0, 1, . . . , ⌊log |Si |⌋. Finally, it stores the 1-mismatch sketches of Si [1, δj ],
where δj is the remainder of −2i modulo ρj . To compute the periods and
the sketches during the preprocessing step we make three passes over the pattern. Over the first two passes we compute the minimal periods of Pi [1, 2i−1 ]
and Si [1, 2j ] for all i and j using O(log2 m) instances of the streaming algorithm [13] (the algorithm can compute the minimal period in one pass if
it is small, but requires two passes if the period is large). During the third
pass we compute the 1-mismatch sketches.
Lemma 3.6. The algorithm can decide if a position ℓ in level j is preceded by
a right-half 1-mismatch occurrence of Pi in O(log3 m/ log log m) time and, if
this is the case, it can also compute the 1-mismatch sketches of T [1, ℓ−2i −1]
and T [1, ℓ − 1].
Proof. We consider three cases based on the relationship between ℓ and the
positions ℓaj .
15

Case 1: ℓ < ℓ1j or ℓaj + 2i−2 ≤ ℓ < ℓa+1
for some a ∈ {1, 2, 3}. In this case
j
ℓ cannot be preceded by a 1-mismatch occurrence of Pi by definition.
Case 2: ℓaj ≤ ℓ < ℓaj + 2i−2 . Below we explain how to compute the
1-mismatch sketches of T [ℓ − 2i , ℓ − 1] in O(log3 m/ log log m) time. The
algorithm can then use these sketches and the ones of Pi to determine in
O(log2 m/ log log m) time whether ℓ is preceded by a right-half 1-mismatch
occurrence of Pi .
First, the algorithm computes the 1-mismatch sketches of T [1, ℓ − 2i − 1]
by extensively using Lemma 3.3. Recall that ℓaj is preceded by a righthalf 1-mismatch occurrence of Pi . If the same property holds for ℓ, then
T [ℓaj − 2i , ℓaj − 2i−1 − 1] and T [ℓ − 2i , ℓ − 2i−1 − 1] are two occurrences of
Pi [1, 2i−1 ] that overlap by at least 2i−2 positions; see Fig. 1. Therefore
T [ℓaj − 2i , ℓ − 2i − 1] is a power of the minimal period of Pi [1, 2i−1 ] by Fine
and Wilf’s periodicity lemma [12]. The algorithm stores the 1-mismatch
sketches of T [1, ℓaj − 2i − 1] and it can compute the 1-mismatch sketches of
T [ℓaj − 2i , ℓ − 2i − 1] from the 1-mismatch sketches of the minimal period
of Pi [1, 2i−1 ] in O(log3 m/ log log m) time. Therefore, it can compute the
1-mismatch sketches of T [1, ℓ − 2i − 1] in O(log3 m/ log log m) time.
Second, the algorithm computes the 1-mismatch sketches of T [1, ℓ − 1]
using the 1-mismatch sketches of T [1, ℓj − 1] and of the minimal period of
Si [1, 2j ] in O(log3 m/ log log m) time. Finally, the algorithm computes the
1-mismatch sketches of T [ℓ − 2i , ℓ − 1] in O(log2 m/ log log m) time using the
1-mismatch sketches of T [1, ℓ − 2i − 1] and T [1, ℓ − 1].
Pi [1, 2i−1 ]
Pi [1, 2i−1 ]

ℓaj − 2i

ℓaj

ℓ − 2i

ℓ

Figure 1: Case 2 of Lemma 3.6. Position ℓ is close to one of the positions ℓaj .

Case 3: ℓ ≥ ℓ1j + 2i . In this case T [ℓ − 2i , ℓ − 1] is a suffix of T [ℓ1j , ℓ − 1],
which is a power of the minimal period of Si [1, 2j ], that is, Si [1, ρj ]. As we
know the 1-mismatch sketches of T [1, ℓ1j − 1], Si [1, ρj ], and Si [1, δj ] (recall
16

that δj is the remainder of −2i modulo ρj ), the algorithm can use Lemma 3.3
to compute the 1-mismatch sketches of T [1, ℓ − 1] (by extending T [1, ℓ1j − 1]
with a power of Si [1, ρj ]) and T [ℓ − 2i , ℓ − 2i − 1] (by subtracting the sketches
of Si [1, δj ] from the sketches of a power of Si [1, ρj ]) in O(log3 m/ log log m)
time. It can then use them to determine whether T [ℓ − 2i , ℓ − 1] is a 1mismatch occurrence of Pi .
The algorithm uses the lemma both to compile the output and to update
the levels. When the algorithm encounters a position in the top level that
is preceded by a right-half 1-mismatch occurrence of Pi and followed by an
exact occurrence of Si , the algorithm outputs it together with the required
difference of symbols, which is computed from the 1-mismatch sketches using
Lemma 3.5. Let us show how the algorithm updates the levels. When
a new symbol T [q] arrives and T [q] = Si [1], the algorithm adds q to the
level 0. If q is preceded by a right-half 1-mismatch occurrence of Pi , then
the algorithm also tries to update the ℓa0 values and possibly retains the
1-mismatch sketches of T [1, q − 2i − 1] and T [1, q − 1] output by the first
process. The algorithm then updates each of the remaining levels in turn.
To update level j, it considers the leftmost position ℓj in this level. If the
Rabin-Karp fingerprints imply that it is an occurrence of Si [1, 2j+1 ], the
algorithm promotes it to the next level, and otherwise discards it. In the
former case the algorithm uses Lemma 3.6 to check whether ℓj is preceded
by a right-half 1-mismatch occurrence of Pi . If it does, it computes the
1-mismatch sketches and updates the positions ℓaj+1 .
Complexity. Recall that for each i = 0, 1, . . . , ⌈log m⌉ we run two processes in parallel. The bottleneck of the first process is the 1-Mismatch
algorithm; it uses O(log4 m/ log log m) space and O(log3 m/ log log m) time
per symbol. The time complexity of the second process is bounded by
O(log m) applications of the algorithm of Lemma 3.6 (one per level) and
is O(log4 m/ log log m) per symbol. The space complexity of the second
process is O(log3 m/ log log m). Therefore, our 1-Mismatch with Error
Correcting algorithm uses O(log5 m/ log log m) space and time per symbol.

3.2

Proof of Theorem 1.2: general value of k

Theorem 1.2 follows from Theorem 1.1 via a randomised reduction. The
first variant of this reduction, which was deterministic, was presented by
Porat and Porat [18], who used it to reduce the k-Mismatch problem to
17

the 1-Mismatch problem. It was further made more space-efficient at a
return of slightly higher error probability by Clifford et al. [8]. The main
idea of this reduction is to consider a number of partitions of the pattern into
O(k log2 m) subpatterns. By defining the partitions appropriately, we can
guarantee that at each alignment where the Hamming distance is small, each
mismatch will correspond to a 1-mismatch occurrence of some subpattern.
This lets us apply the 1-Mismatch with Error Correcting algorithm
to find all such alignments and to restore the data for them. We give a full
description of the reduction below.
We start by filtering out the locations where the Hamming distance is
large. To this end, we use a randomised algorithm for the following 2approximate k-mismatch problem. Let H be the true Hamming distance at
a particular alignment of the pattern and the text. The algorithm outputs
“Yes” if H ≤ k, either “Yes” or “No” if k < H ≤ 2k, and “No” if H > 2k.
Lemma 3.7 ([8]). Given a pattern P of length m and a streaming text
arriving one symbol at a time, there is a randomised O(k 2 log6 m)-space
algorithm which takes O(log5 m) worst-case time per arriving symbol and
solves the 2-approximate k-mismatch problem. The probability of error is at
most 1/m2 .
Next, we consider ℓ = ⌊log m⌋ partitions of the pattern into equispaced
subpatterns. More precisely, we select ℓ random primes from the interval
[k log2 m, 34k log2 m]. For each prime pi the pattern P is then partitioned
into pi subpatterns Pi,j = P [j]P [pi + j]P [2pi + j] . . ., where j = 1, . . . , pi .
Consider a particular location q in the text and the set of all mismatches
between P and T [q −m+1, q]. Let us call a mismatch isolated if it is the only
mismatch between some subpattern Pi,j and the corresponding subsequence
of T [q − m + 1, q], and let Mq be the set of all isolated mismatches at an
alignment q.
Lemma 3.8 ([8]). If |Mq | ≤ 2k, the set Mq contains all mismatches between
P and T [q − m + 1, q] with probability at least 1 − 1/m2 .
To finalize the reduction, we partition the text T into pi equispaced substreams Ti,j , where j = 1, . . . , pi , for each primePpi . We run the 1-Mismatch
with Error Correcting algorithm for all i p2i = O(k2 log5 m) subpattern/substream pairs (Pi,j1 , Ti,j2 ). At each location where the algorithm
for the 2-approximate problem outputs “Yes”, we retrieve all isolated mismatches and the data using the appropriate pi instances of the 1-Mismatch
with Error Correcting problem for each i. This completes the de18

scription of our solution to the k-Mismatch with Error Correcting
problem.
In total, we use O(k2 log10 m/ log log m) space. To analyse the time
complexity, note that when a new symbol of T arrives, we need to send it to
O(log m) substreams only (one for each prime) and run the next step for each
of the O(k log2 m) instances of the 1-Mismatch with Error Correcting
problem on each of these substreams, which requires O(k log8 m/ log log m)
time per symbol.

References
[1] Amihood Amir, Eran Chencinski, Costas S. Iliopoulos, Tsvi
Kopelowitz, and Hui Zhang. Property matching and weighted matching. Theor. Comput. Sci., 395(2-3):298–310, 2008.
[2] Amihood Amir, Costas Iliopoulos, Oren Kapah, and Ely Porat. Approximate matching in weighted sequences. In CPM’06: Proc. of the
17th Annual Symposium on Combinatorial Pattern Matching, volume
4009 of LNCS, pages 365–376, 2006.
[3] Carl Barton, Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski. Efficient index for weighted sequences. In CPM’16: Proc.
of the 27th Annual Symposium on Combinatorial Pattern Matching,
LIPIcs, pages 4:1–4:13, 2016.
[4] Carl Barton and Solon P. Pissis. Linear-time computation of prefix table
for weighted strings. In WORDS’15: Proc. of the 10th International
Conference on Combinatorics on Words, volume 9304 of LNCS, pages
73–84, 2015.
[5] Sudip Biswas, Manish Patil, Sharma V. Thankachan, and Rahul Shah.
Probabilistic threshold indexing for uncertain strings. In EDBT’16:
Proc. of the 19th International Conference on Extending Database Technology, pages 401–412, 2016.
[6] Dany Breslauer and Zvi Galil. Real-time streaming string-matching.
In CPM’11: Proc. of the 22nd Annual Symposium on Combinatorial
Pattern Matching, volume 6661 of LNCS, pages 162–172, 2011.
[7] Manolis Christodoulakis, Costas S. Iliopoulos, Laurent Mouchard, and
Kostas Tsichlas. Pattern matching on weighted sequences. In CompBioNets’04: Proc. of the 1st International Conference on Algorithms
19

and Computational Methods for Biochemical and Evolutionary Networks, KCL publications, 2004.
[8] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya. The k -mismatch problem revisited. In SODA’16:
Proc. of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2039–2052, 2016.
[9] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana A. Starikovskaya. Dictionary matching in a stream. In ESA’15:
Proc. of the 23rd Annual European Symposium on Algorithms, volume
9294 of LNCS, pages 361–372, 2015.
[10] Raphaël Clifford, Markus Jalsenius, Ely Porat, and Benjamin Sach.
Space lower bounds for online pattern matching. Theor. Comput. Sci.,
483:58–74, 2013.
[11] Raphaël Clifford and Tatiana Starikovskaya. Approximate Hamming
distance in a stream. In ICALP’16: Proc. of the 43rd International
Colloquium on Automata, Languages, and Programming, LIPIcs, pages
20:1–20:13, 2016.
[12] Maxime Crochemore, Christophe Hancart, and Thierry Lecroq. Algorithms on Strings. Cambridge University Press, 2007.
[13] Funda Ergün, Hossein Jowhari, and Mert Saglam. Periodicity in
streams. In APPROX’10: Proc. of the 13th International Workshop
on Approximation, Randomization, and Combinatorial Optimization,
volume 6302 of LNCS, pages 545–559, 2010.
[14] Costas S. Iliopoulos, Christos Makris, Yannis Panagis, Katerina
Perdikuri, Evangelos Theodoridis, and Athanasios K. Tsakalidis. The
weighted suffix tree: An efficient data structure for handling molecular
weighted sequences and its applications. Fundam. Inform., 71(2-3):259–
277, 2006.
[15] Richard M. Karp and Michael O. Rabin. Efficient randomized patternmatching algorithms. IBM J. of Research and Development, 31(2):249–
260, 1987.
[16] Tomasz Kociumaka, Solon P. Pissis, and Jakub Radoszewski. Pattern
matching and consensus problems on weighted sequences and profiles.
In Proceedings of the 27th International Symposium on Algorithms and
Computation, ISAAC 2016. To appear, 2016.
20

[17] Cinzia Pizzi and Esko Ukkonen. Fast profile matching algorithms - A
survey. Theor. Comput. Sci., 395(2-3):137–157, 2008.
[18] Benny Porat and Ely Porat. Exact and approximate pattern matching in the streaming model. In FOCS’09: Proc. of the 50th Annual
Symposium on Foundations of Computer Science, pages 315–323, 2009.
[19] Ely Porat and Ohad Lipsky. Improved sketching of hamming distance
with error correcting. In CPM’07: Proc. of the 18th Annual Conference
on Combinatorial Pattern Matching, volume 4580 of LNCS, pages 173–
182, 2007.
[20] Albin Sandelin, Wynand Alkema, Pär Engström, Wyeth W. Wasserman, and Boris Lenhard. JASPAR: an open-access database for eukaryotic transcription factor binding profiles. Nucl. Acids Res., 32(1):D91–
D94, 2004.
[21] Xuhua Xia. Position weight matrix, Gibbs sampler, and the associated
significance tests in motif characterization and prediction. Scientifica,
2012. Article ID 917540.

21

