DIENS, École normale supérieure de Paris, PSL Research University, France and
LaBRI, Université de Bordeaux,
Francegabriel.bathie@gmail.comhttps://orcid.org/0000-0003-2400-4914 Birkbeck,
University of London,
UKpcharalampo@gmail.comhttps://orcid.org/0000-0002-6024-1557A research visit
during which part of the presented ideas were conceived was funded by a Royal
Society International Exchanges Award. DIENS, École normale supérieure de
Paris, PSL Research University,
Francetat.starikovskaya@gmail.comhttps://orcid.org/0000-0002-7193-9432Partially
supported by the grant ANR-20-CE48-0001 from the French National Research
Agency (ANR). Gabriel Bathie, Panagiotis Charalampopoulos and Tatiana
Starikovskaya [500]Theory of computation Pattern matching John Q. Open and
Joan R. Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT
2016 CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Pattern Matching with Mismatches and Wildcards

Gabriel Bathie  Panagiotis Charalampopoulos  Tatiana Starikovskaya

###### Abstract

In this work, we address the problem of approximate pattern matching with
wildcards. Given a pattern $P$ of length $m$ containing $D$ wildcards, a text
$T$ of length $n$, and an integer $k$, our objective is to identify all
fragments of $T$ within Hamming distance $k$ from $P$.

Our primary contribution is an algorithm with runtime
$\mathcal{O}(n+(D+k)(G+k)\cdot n/m)$ for this problem. Here, $G\leq D$
represents the number of maximal wildcard fragments in $P$. We derive this
algorithm by elaborating in a non-trivial way on the ideas presented by
[Charalampopoulos et al., FOCS’20] for pattern matching with mismatches
(without wildcards). Our algorithm improves over the state of the art when
$D$, $G$, and $k$ are small relative to $n$. For instance, if $m=n/2$,
$k=G=n^{2/5}$, and $D=n^{3/5}$, our algorithm operates in $\mathcal{O}(n)$
time, surpassing the $\Omega(n^{6/5})$ time requirement of all previously
known algorithms.

In the case of _exact_ pattern matching with wildcards ($k=0$), we present a
much simpler algorithm with runtime $\mathcal{O}(n+DG\cdot n/m)$ that clearly
illustrates our main technical innovation: the utilisation of positions of $P$
that do not belong to any fragment of $P$ with a density of wildcards much
larger than $D/m$ as anchors for the sought (approximate) occurrences.
Notably, our algorithm outperforms the best-known $\mathcal{O}(n\log m)$-time
FFT-based algorithms of [Cole and Hariharan, STOC’02] and [Clifford and
Clifford, IPL’04] if $DG=o(m\log m)$.

We complement our algorithmic results with a structural characterization of
the $k$-mismatch occurrences of $P$. We demonstrate that in a text of length
$\mathcal{O}(m)$, these occurrences can be partitioned into
$\mathcal{O}((D+k)(G+k))$ arithmetic progressions. Additionally, we construct
an infinite family of examples with $\Omega((D+k)k)$ arithmetic progressions
of occurrences, leveraging a combinatorial result on progression-free sets
[Elkin, SODA’10].

###### keywords:

pattern matching, wildcards, mismatches, Hamming distance, don’t cares

##  1 Introduction

Pattern matching is one of the most fundamental algorithmic problems on
strings. Given a text $T$ of length $n$ and a pattern $P$ of length $m$, both
over an alphabet $\Sigma$, the goal is to compute all occurrences of $P$ in
$T$. This problem admits an efficient linear-time solution, for example using
the seminal algorithm of Knuth, Morris, and Pratt [32]. However, looking for
exact matches of $P$ in $T$ can be too restrictive for some applications, for
example when working with potentially corrupted data, when accounting for
mutations in genomic data, or when searching for an incomplete pattern. There
are several ways to model and to work with corrupt or partial textual data for
the purposes of pattern matching.

A natural and well-studied problem is that of computing fragments of the text
that are close to the pattern with respect to some distance metric. One of the
most commonly used such metrics is the Hamming distance. Abrahamson and
Kosaraju [1, 35] independently developed an algorithm based on convolutions
via the Fast Fourier Transform (FFT) that computes the Hamming distance
between the pattern and every $m$-length substring of the text. It runs in
time $\mathcal{O}(n\sqrt{m\log m})$, and this complexity has only been
recently improved by a $\sqrt{\log m}$ factor by Chan et al. [10]. In many
applications, one is interested in computing substrings of the text that are
_close_ to the pattern instead of computing the distance to every substring.
In this case, an integer threshold $k$ is given as part of the input and the
goal is to compute fragments of $T$ that have at most $k$ mismatches with $P$.
Such a fragment is called a _$k$ -mismatch occurrence_ of $P$ in $T$. The
state-of-the-art for this problem are the $\mathcal{O}(n\sqrt{k\log k})$-time
algorithm of Amir et al. [3], the $\mathcal{O}(n+(n/m)\cdot k^{2})$-time
algorithm of Chan et al. [9], and the $\mathcal{O}(n+kn/\sqrt{m})$-time
algorithm of Chan et al. [10] that provides a smooth trade-off between the two
aforementioned solutions, improving the bound for some range of parameters.
Earlier deterministic counterparts of the aforementioned algorithms (which are
randomised) at the expense of extra polylogarithmic factors can be found in
[16, 25, 12].

The structure of the set of $k$-mismatch occurrences of $P$ in $T$ admits an
insightful characterisation, shown by Charalampopoulos et al. [12] who
tightened the result of Bringmann et al. [7]: either $P$ has
$\mathcal{O}(k\cdot n/m)$ $k$-mismatch occurrences in $T$ or $P$ is at Hamming
distance less than $2k$ from a string with period $q=\mathcal{O}(m/k)$;
further, in the periodic case, the starting positions of the $k$-mismatch
occurrences of $P$ in $T$ can be partitioned into $\mathcal{O}(k^{2}\cdot
n/m)$ arithmetic progressions with difference $q$. This characterisation can
be exploited towards obtaining efficient algorithms in settings other than the
standard one, e.g., in the setting where both $P$ and $T$ are given in
compressed form [12], and, in combination with other ideas and techniques, in
the streaming setting [33] and in the quantum setting [29].

In the case when the positions of the corrupt characters in the two strings
are known in advance, one can use a more adaptive approach, by placing a
_wildcard_ character
$\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>in each of these positions, and then performing exact pattern matching.
Wildcards (also called “don’t cares” or “holes”) are special characters that
match any character in
$\Sigma\cup\\{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>akin to the “?” in UNIX shell commands or the “.” operator in regular
expressions engines. Already in 1974, Fischer and Paterson [39] presented an
$\mathcal{O}(n\log m\log\sigma)$-time algorithm for the pattern matching
problem with wildcards. Subsequent works by Indyk [28], Kalai [30], and Cole
and Hariharan [18] culminated in an $\mathcal{O}(n\log m)$-time deterministic
algorithm [18]. A few years later, Clifford and Clifford [13] presented a very
elegant algorithm with the same complexities. All the above solutions are
based on fast convolutions via the FFT.

Unsurprisingly, the pattern matching problem in the case where we both have
wildcards and allow for mismatches has also received significant attention.
Conceptually, it covers the case where some of the corrupt positions are
known, but not all of them. We denote by $D$ the total number of wildcards in
$P$ and $T$, and by $G$ the number of maximal fragments in $P$ and $T$ all of
whose characters are wildcards. A summary of known results for the considered
problem is provided in Table 1.

Note that, in practice, $G$ may be much smaller than $D$. For example, DNA
sequences have biologically important loci, which are characterised using the
notion of structured motifs [38]: sequences of alternating conserved and non-
conserved blocks. Conserved blocks are ones which are identical across intra-
or inter-species occurrences of the structured motif, while non-conserved ones
are not known to have biological significance and can vary significantly
across such occurrences. Non-conserved blocks can be hence modelled with
blocks of wildcards as in [37]. In this case, evidently, we have $G$ being
much smaller than $D$. This feature has been used in the literature before,
for example, for the problem of answering longest common compatible prefix
queries over a string with wildcards. In particular, Crochemore et al. [20]
showed an $\mathcal{O}(n+nG)$-time construction algorithm for a data structure
that is capable of answering such queries in constant time, while the
previously best known construction time was $\mathcal{O}(n+nD)$ [6].

In several applications, it is sufficient to only account for wildcards in one
of $P$ and $T$: in the application we just discussed, the text is a fixed DNA
sequence, whereas the sought pattern, the structured motif, is modelled as a
string with wildcards. In such cases, one can obtain more efficient solutions
than those for the general case where both $P$ and $T$ have wildcards, such as
the ones presented in [17, 41] and the one we present here.

Time complexity |  cc$\lozenge$$\blacklozenge$ in | Reference
---|---|---
$\mathcal{O}(n(k+\log m\log k)\log n)$ w.h.p. | $P$ and $T$ | [15]
$\mathcal{O}(nk^{2}\log^{2}m)$ | [15]
$\mathcal{O}(nk\operatorname{polylog}m)$ | [14, 15]
$\mathcal{O}(n\sqrt{m\log m})$ | follows from [1, 35], cf. [15]
$\mathcal{O}(n\sqrt{m-D}\log m)$ | [3]
$\mathcal{O}(nk\operatorname{polylog}m)$ w.h.p. | [40]
$\mathcal{O}(n\sqrt[3]{mk\log^{2}m})$ | one of $P$ or $T$ | [17]
$\mathcal{O}(n\sqrt{k\log m}+n\cdot\min\\{\sqrt[3]{Gk\log^{2}m},\sqrt{G\log m}\\})$ | $P$ | [41]
Table 1: Previous results on pattern matching with wildcards under the Hamming
distance.

##### Multi-framework algorithms with the PILLAR model.

We describe our algorithms in the PILLAR model, introduced by Charalampopoulos
et al. [12]. In this model, we account for the number of calls to a small set
of versatile primitive operations on strings, called PILLAR operations, such
as longest common extension queries or internal pattern matching queries, plus
any extra time required to perform usual word RAM operations. The PILLAR
operations can be implemented with different preprocessing/operation time
trade-offs. For example, in the word RAM model, if the input strings are given
explicitly and have total length $n$, one can build in $\mathcal{O}(n)$ time a
data structure that allows performing PILLAR operations in constant time. In
this setting, an algorithm using $p$ PILLAR operations plus $t$ additional
time takes a total of $\mathcal{O}(n+p+t)$ time. The PILLAR model allows for a
unified approach across several settings, due to known efficient
implementations of PILLAR operations. These settings include the compressed
setting, where the strings are compressed as straight-line programs, the
dynamic setting [24], and the quantum setting. Therefore, in essence, we
provide meta-algorithms, that can be combined with efficient PILLAR
implementations to give efficient algorithms for a variety of settings.

##### The standard trick.

For reasons related to the periodic structure of strings, it is often
convenient to assume that the length of the text is at most $3m/2$, where $m$
is the length of the pattern. This does not pose any actual restrictions as
one can cover $T$ with $\mathcal{O}(n/m)$ fragments of $T$, each of length
$3m/2$ (except maybe the last one) such that each two consecutive fragments
overlap on $m-1$ positions. Then, any occurrence of $P$ in $T$ is contained in
exactly one of these fragments. Thus, an algorithm with runtime $C(m)$ for a
pattern of length $m$ and a text of length at most $3m/2$, readily implies an
algorithm with runtime $\mathcal{O}(C(m)\cdot n/m)$ for texts of length $n$,
as one can run $\mathcal{O}(n/m)$ separate instances and aggregate the
results.

##### Reduction to pattern matching with mismatches.

The problem of $k$-mismatch pattern matching with $D$ wildcards can be
straightforwardly reduced to $(D+k)$-mismatch pattern matching in _solid
strings_ , i.e., strings without wildcards. In what follows we consider solid
texts. Given the pattern $P$, construct the string $P_{\\#}$ obtained by
replacing every wildcard in $P$ with a new character $\\#\notin\Sigma$.

A pattern $P$ with $D$ wildcards has a $k$-mismatch occurrence at a position
$i$ of a solid text $T$ if and only if $P_{\\#}$ has a $(D+k)$-mismatch
occurrence at that position.

In [12], the authors present an efficient algorithm for the $d$-mismatch
pattern matching problem for solid strings in the PILLAR model.

######  Theorem 1.1 ([12, Main Theorem 8]).

Let $S$ and $T$ be solid strings of respective lengths $m$ and $n\leq 3m/2$.
We can compute a representation of the $d$-mismatch occurrences of $S$ in $T$
using $\mathcal{O}(d^{2}\log\log d)$ time plus $\mathcal{O}(d^{2})$ PILLAR
operations.

Applying Theorem 1.1 with $S=P_{\\#}$ and $d=D+k$, we obtain an algorithm for
$k$-mismatch pattern matching with $D$ wildcards that runs in
$\tilde{\mathcal{O}}((D+k)^{2})$ time in the PILLAR model.111In this work, the
notation $\tilde{\mathcal{O}}(\cdot)$ suppresses factors polylogarithmic in
the length of the input strings.

##### Our results.

We manage to provide a more fine-grained result, replacing one $D$ factor with
a $G$ factor. We also make an analogous improvement over the structural result
for the set of $k$-mismatch occurrences obtained via the reduction to
$(D+k)$-mismatch pattern matching. Our main result can be formally stated as
follows.

######  Theorem 1.2.

Let $P$ be a pattern of length $m$ with $D$ wildcards arranged in $G$ groups,
$T$ be a solid text of length $n\leq 3m/2$, and $k$ be a positive integer. We
can compute a representation of the $k$-mismatch occurrences of $P$ in $T$ as
$\mathcal{O}((D+k)G)$ arithmetic progressions with common difference and
$\mathcal{O}((D+k)k)$ additional occurrences using
$\mathcal{O}((D+k)\cdot(G+k)\log\log(D+k))$ time plus
$\mathcal{O}((D+k)\cdot(G+k))$ PILLAR operations.

In the usual word RAM model, by using known implementations of the PILLAR
operations with $O(n)$ preprocessing time and $O(1)$ operation time, using the
“standard trick”, and observing that the loglogarithmic factor can be avoided
at the cost of $\mathcal{O}(n)$ extra time, we obtain an algorithm with
runtime $\mathcal{O}(n+(m/n)(D+k)(G+k))$ for texts of arbitrary length $n$.
Appendix C details the implementation of our algorithm in other settings, such
as the dynamic and compressed settings. For example, given a solid text $T$
and a pattern $P$ with $D$ wildcards represented as straight-line programs of
sizes $N$ and $M$ respectively, we can compute the number of $k$-mismatch
occurrences of $P$ in $T$ in time $\tilde{\mathcal{O}}(M+N\cdot(D+k)(G+k))$,
without having to uncompress $P$ and $T$.

We complement our structural result with a lower bound on the number of
arithmetic progressions of occurrences of a pattern with mismatches and
wildcards (Theorem 5.1). Informally, we show that there exists a pattern $P$
and a text $T$ of length at most $3|P|/2$ such that the set of $k$-mismatch
occurrences of $P$ in $T$ cannot be covered with less than
$\Omega((D+k)\cdot(k+1))$ arithmetic progressions. This implies, in
particular, a lower bound of $\Omega(D)$ on the number of arithmetic
progressions of exact occurrences for a pattern with $D$ wildcards and a lower
bound of $\Omega(k^{2})$ on the number of arithmetic progressions of
$k$-mismatch occurrences of a solid pattern, thus showing the tightness of the
known upper bound [12].

When $k=0$, Theorem 1.2 readily implies an $\mathcal{O}(n+DG\cdot n/m)$-time
algorithm for _exact_ pattern matching. However, the techniques employed by
this algorithm are rather heavy-handed, and this can be avoided. In Section 3,
we present a much simpler algorithm that achieves the same time complexity and
showcases the primary technical innovation of our approach: the utilization of
carefully selected positions, termed _sparsifiers_ , which exclusively belong
to fragments $F$ of $P$ such that the ratio of the number of wildcards within
them to their length is bounded by $\mathcal{O}(D/m)$. In the standard word
RAM model, the implied $\mathcal{O}(n+DG\cdot n/m)$ time complexity for exact
pattern matching outperforms the state-of-the-art $\mathcal{O}(n\log m)$ [13,
18] when $DG=o(m\log m)$.

##### Technical overview.

To illustrate how sparsifiers help, consider our algorithm for exact pattern
matching, which draws ideas from the work of Bringmann et al. [7]. We first
compute a solid $\Omega(m/G)$-length fragment $S$ of $P$ that contains a
sparsifier. We then compute its exact matches in $T$. If $S$ only has a few
occurrences, we straightforwardly verify which of those extend to occurrences
of $P$. However, if $S$ has many occurrences we cannot afford to do that, and
we instead have to exploit the implied periodic structure of $S$. We
distinguish between two cases. In the case when $P$ matches a periodic string
with the same period as $S$, denoted $\textsf{per}(S)$, we take a sliding
window approach as in [7], using the fact that the wildcards are organised in
only $G$ groups. The remaining case poses the main technical challenge. In
that case, our goal is to align the maximal fragment
$S^{\prime}:=P[i\mathinner{.\,.}j]$ of $P$ that contains $S$ and matches a
solid string with period $\textsf{per}(S)$ with a periodic fragment of $T$
such that position $i-1$ is aligned with a position breaking the periodicity
in $T$; a so-called _misperiod_. To this end, we compute $\mathcal{O}(G)$
maximal fragments of $T$, called $S$-runs, that have period $\textsf{per}(S)$.
The issue is, however, that up to $D$ misperiods in $T$ might be aligned with
wildcards of $S^{\prime}$. A straightforward approach would be to extend each
$S$-run to the left, allowing for $D+1$ misperiods and to try aligning each
such misperiod with $i-1$. This would yield an algorithm with runtime
$\mathcal{O}(G^{2}D)$ in the PILLAR model, as we would have $\mathcal{O}(DG)$
candidate misperiods to align position $i-1$ with, and the verification time
for each such alignment is $\mathcal{O}(G)$. The crucial observation is that
since $S^{\prime}$ contains a sparsifier, we do not need to extend each
$S$-run allowing for $D+1$ misperiods. Instead, we extend it while the ratio
of the encountered misperiods to its length does not exceed $c\cdot D/m$, for
some constant $c$. By skipping any $S$-runs that are covered due to the
extension of other $S$-runs, we ensure that the total number of misperiods
with which we align $i-1$ is $\mathcal{O}(D)$ in total, instead of
$\mathcal{O}(DG)$. This yields the desired complexity.

As for handling mismatches, we follow the framework of Charalampopoulos et al.
[12] for $k$-mismatch pattern matching on solid strings. They showed that an
efficient structural analysis of a solid pattern can return a number of so-
called _breaks_ or a number of so-called _repetitive regions_ , or conclude
that the pattern is _almost periodic_. They treated each of the three cases
separately, exploiting the computed structure. We make several alterations to
account for wildcards, such as ensuring that breaks are solid strings and
adapting the sliding window approach. The primary technical challenge in
achieving an efficient solution lies in limiting the number of occurrences of
repetitive regions in $T$. The greater the number of repetitive region
occurrences, the higher the number of potential starting positions for
$k$-mismatch occurrences of $P$. We achieve that by ensuring that each
repetitive region contains a sparsifier. This way, we force an upper bound on
the number of wildcards in each repetitive region, which, in turn, allows us
to bound the number of its approximate occurrences in $T$.

Our lower bound is based on a neat construction that employs large sets that
do not contain any arithmetic progression of size 3 [22, 5, 21]. We use these
sets to construct the pattern $P$ and the text $T$. They consist mostly of
$0$s, except that $P$ contains wildcards and $1$s positioned at indices that
form a progression-free set, and $T$ contains $0$s also positioned at indices
that form a progression-free set, but that are far apart from each other. Our
construction ensures that there is a $k$-mismatch occurrence of $P$ at
position $i$ in $T$ if and only if a $1$ or a wildcard of $P$ is aligned with
a $1$ of $T$. We show that the set of such positions $i$ has size
$\Omega((D+k)\cdot(k+1))$ and is progression-free.

##### Organisation of the paper.

Section 2 introduces concepts relevant to this work, as well as an abstract
problem that we use in our analysis. Section 3 presents an algorithm for exact
pattern matching with wildcards in the PILLAR model. It illustrates some of
the main ideas underlying this work, without having to handle mismatches,
which bring further challenges. In Section 4, we describe the algorithm that
underlies Theorem 1.2; the implications of this theorem in different settings
are provided in Appendix C. We conclude with Section 5 where we present our
structural lower bound, thus proving Theorem 5.1.

##  2 Preliminaries

In this work, $\Sigma$ denotes an alphabet that consists of integers
polynomially bounded in the length of the input strings. The elements of
$\Sigma$ are called _(solid) characters_. Additionally, we consider a special
character denoted by  cc$\lozenge$$\blacklozenge$ that is not in $\Sigma$ and
is called a _wildcard_. Let
$\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color@gray@fill{0.9}$\blacklozenge$}}}}=\Sigma\cup\\{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>Two characters match if (a) they are identical or (b) at least one of them is
a wildcard. Two equal-length strings match if and only if their $i$-th
characters match for all $i$.

For an integer $n\geq 0$, we denote the set of all length-$n$ strings over an
alphabet $A$ by $A^{n}$. The set of all strings over $A$ is denoted by
$A^{*}$. The unique empty string is denoted by $\varepsilon$. A string in
$\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>is called _solid_ if it only contains solid characters, i.e., it does not
contain wildcards.

For two strings
$S,T\in\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>we use $ST$ to denote their concatenation. For an integer $m>0$, the string
obtained by concatenating $m$ copies of $S$ is denoted by $S^{m}$. We denote
by $S^{\infty}$ the string obtained by concatenating infinitely many copies of
$S$.

For a string
$T\in\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>and an index $i\in[1\mathinner{.\,.}n]$,222For integers $i,j\in\mathbb{Z}$,
denote $[i\mathinner{.\,.}j]=\\{k\in\mathbb{Z}:i\leq k\leq j\\}$,
$[i\mathinner{.\,.}j)=\\{k\in\mathbb{Z}:i\leq k<j\\}$. the $i$-th character of
$T$ is denoted by $T[i]$. We use $|T|=n$ to denote the length of $T$. For
indices $1\leq i,j\leq n$, $T[i\mathinner{.\,.}j]$ denotes the _fragment_
$T[i]T[{i+1}]\cdots T[j]$ of $T$ if $i\leq j$ and the empty string otherwise.
We extend this notation in a natural way to
$T[i\mathinner{.\,.}j+1)=T[i\mathinner{.\,.}j]=T(i-1\mathinner{.\,.}j]$. When
$i=1$ or $j=n$, we omit these indices, i.e.,
$T[\mathinner{.\,.}j]=T[1\mathinner{.\,.}j]$ and
$T[i\mathinner{.\,.}]=T[i\mathinner{.\,.}n]$. A string $P$ is a _prefix_ of
$T$ if there exists $j\in[1\mathinner{.\,.}n]$ such that
$P=T[\mathinner{.\,.}j]$, and a _suffix_ of $T$ if there exists
$i\in[1\mathinner{.\,.}n]$ such that $P=T[i\mathinner{.\,.}]$. A _ball_ with a
radius $r$ and a center $i$, $B_{T}(i,r)$ is a fragment
$T[\max\\{1,i-r\\}\mathinner{.\,.}\min\\{i+r,n\\}]$, where we often omit the
subscript $T$ if it is clear from the context. A position $i$ of a string $T$
is called an _occurrence_ of a string $P$ if $T[i\mathinner{.\,.}i+|P|)=P$.

A positive integer $\rho$ is a _period_ of a (solid) string $T\in\Sigma^{n}$
if $T[i]=T[i+\rho]$ for all $i\in[1\mathinner{.\,.}n-\rho]$. The smallest
period of $T$ is referred to as _the period_ of $T$ and is denoted by
$\textsf{per}(T)$. If $\textsf{per}(T)\leq|T|/2$, $T$ is called _periodic_. We
exploit the following folklore fact, which is a straightforward corollary of
the Fine–Wilf periodicity lemma [23]:

######  Corollary 2.1 (folklore).

Let $P,T\in\Sigma^{*}$ be solid strings such that $|T|<2|P|$. The set of
occurrences of $P$ in $T$ can be represented as one arithmetic progression
(possibly, trivial) with difference equal to $\textsf{per}(P)$.

For an integer $s\in[1\mathinner{.\,.}n)$, we denote by $\textsf{rot}^{s}(T)$
the string $T[s+1]\cdots T[n]T[1]\cdots T[s]$, while $\textsf{rot}^{0}(T):=T$.
More generally, for any $s\in\mathbb{Z}$, we denote by $\textsf{rot}^{s}(T)$
the string $\textsf{rot}^{x}(T)$, where $x=s\bmod{|T|}$. A non-empty (solid)
string is called _primitive_ if it is different from each of its non-trivial
rotations.

######  Fact 1 ([19]).

For any solid string $T\in\Sigma^{n}$, the prefix
$T[1\mathinner{.\,.}\textsf{per}(T)]$ is primitive.

An integer $\rho$ is a _deterministic period_ of a string
$S\in\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>(that may contain wildcards), if there exists a solid string $T$ that matches
$S$ and has period $\rho$.

The Hamming distance $\delta_{H}(S_{1},S_{2})$ of two equal-length strings
$S_{1},S_{2}$ in
$\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>is the number of positions $i$ such that $S_{1}[i]$ does not match $S_{2}[i]$.
For two strings
$U,Q\in\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>we slightly abuse notation and denote
$\delta_{H}(U,Q^{\infty}[\mathinner{.\,.}|U|])$ by $\delta_{H}(U,Q^{\infty})$.
A position $i$ of a string $T$ is called a $k$-mismatch occurrence of a string
$P$ if $\delta_{H}(T[i,i+|P|),P)\leq k$, and the set of all $k$-mismatch
occurrences of $P$ in $T$ is denoted by $\mathrm{Occ}_{k}(P,T)$.

##### The PILLAR model.

The PILLAR model of computation, introduced in [12], abstracts away the
implementation of a versatile set of primitive operations on strings. In this
model, one is given a family of solid strings $\mathcal{X}$ for preprocessing.
The elementary objects are fragments $X[i\mathinner{.\,.}j]$ of strings
$X\in\mathcal{X}$. Each such fragment $S$ is represented via a handle, which
is how $S$ is passed as input to PILLAR operations. Initially, the model
provides a handle to each $X\in\mathcal{X}$. Handles to other fragments can be
obtained through an $\mathsf{Extract}$ operation:

  * •

$\mathsf{Extract}(S,\ell,r)$: Given a fragment $S$ and positions
$1\leq\ell\leq r\leq|S|$, extract $S[\ell\mathinner{.\,.}r]$.

Furthermore, given elementary objects $S,S_{1},S_{2}$ the following primitive
operations are supported in the PILLAR model:

  * •

$\mathsf{Access}(S,i)$: Assuming $i\in[1\mathinner{.\,.}|S|]$, retrieve
$S[i]$.

  * •

$\mathsf{Length}(S)$: Retrieve the length $|S|$ of $S$.

  * •

Longest common prefix $\textsf{lcp}(S_{1},S_{2})$: Compute the length of the
longest common prefix of $S_{1}$ and $S_{2}$.

  * •

$\textsf{lcp}^{R}(S_{1},S_{2})$: Compute the length of the longest common
suffix of $S_{1}$ and $S_{2}$.

  * •

Internal pattern matching $\mathsf{IPM}(S_{1},S_{2})$: Assuming that
$|S_{2}|<2|S_{1}|$, compute the set of the starting positions of occurrences
of $S_{1}$ in $S_{2}$ represented as one arithmetic progression (see Corollary
2.1).

We will make use of the following facts; the proof of the second one is
provided in Appendix A.

######  Fact 2 ([11, proof of Lemma 12]).

The value $\textsf{lcp}(X^{\infty},Z)$ for a fragment $X$ and a suffix $Z$ of
a solid string $Y$ can be computed in $\mathcal{O}(1)$ time in the PILLAR
model.

######  Fact 3.

Let $P$ be a pattern with $D$ wildcards arranged in $G$ groups and $T$ be a
solid text. For a position $p$ and a given threshold $k\geq 0$, one can test
whether $\delta_{H}(P,T[i\mathinner{.\,.}i+m))\leq k$ in $\mathcal{O}(G+k)$
time in the PILLAR model.

In this work, we work in the PILLAR model despite considering strings that
also contain wildcards. We circumvent this by replacing each wildcard with a
solid character $\\#\not\in\Sigma$ and use PILLAR operations over the obtained
collection of (solid) strings. We also ensure that for each string in the
collection we can efficiently compute a linked list that stores the endpoints
of groups of wildcards.

###  2.1 Sparsifiers

In Section 1, we elucidated the pivotal role of the fragments of the pattern
where wildcards exhibit a “typical” distribution. In this section, we
formalize this concept.

######  Definition 2.2 (Sparsifiers).

Consider a string
$P\in\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>containing $D$ wildcards. We call a position $i$ in $X$ a _sparsifier_ if
$X[i]$ is a solid character and, for any $r$, the count of wildcards within
the ball of radius $r$ centered at $i$ is at most $8r\cdot D/m$.

In the following, we demonstrate that $P$ contains a long fragment whose every
position is a sparsifier. We start with an abstract lemma, where one can think
of a binary vector $V$ as the indicator vector for wildcards, and $\|V{\|}$
denotes the number of 1s in $V$. A _run of 1s (resp. 0s)_ is a maximal
fragment that consists only of 1s (resp. 0s).

######  Lemma 2.3.

Let $V$ be a binary vector of size $N$, $M:=\|V{\|}$ and $R$ be the number of
runs of 1s in $V$. Assume $V$ to be represented as a linked list of the
endpoints of runs of 1s in $V$, arranged in the sorted order. There is an
$\mathcal{O}(R)$-time algorithm that computes a set
$U\subseteq[1\mathinner{.\,.}N]$ satisfying each of the following conditions:

  1. 1.

$|U|\geq N/2-M$,

  2. 2.

$U$ can be represented as a union of at most $R+1$ disjoint intervals,

  3. 3.

for each $i\in U$ and radius $r\in[1\mathinner{.\,.}N]$, $\|B_{V}(i,r){\|}\leq
8r\cdot M/N$.

######  Proof 2.4.

First, we scan $V$ from left to right. Each time we see a 1, we mark the
$N/(4M)$ leftmost 0s that are to the right of the considered 1 and have not
been already marked. If we mark the last 0 in $V$, we terminate the scan.
Overall, we mark at most $N/4$ 0s. Next, we perform the symmetric procedure in
a right-to-left scan of $V$.

Let $U$ be the set of positions of unmarked 0s after these two marking steps.
We show that $U$ satisfies the condition of the lemma. First, we have $|U|\geq
N-M-N/2\geq N/2-M$. Secondly, by construction, every run of 0s contains at
most one interval of unmarked positions and hence $U$ can be represented as
union of at most $R+1$ disjoint intervals. Finally, fix $i\in U$ and
$r\in[1\mathinner{.\,.}N]$. Let $B_{1}=V[\max\\{i-r,1\\}\mathinner{.\,.}i-1]$
and $B_{2}=V[i+1\mathinner{.\,.}\min\\{i+r,N\\}]$. Since $V[i]$ was not marked
in the left-to-right scan, there are at least $\|B_{1}{\|}\cdot N/(4M)$ 0s in
$B_{1}$. Symmetrically, since $V[i]$ was not marked in the right-to-left scan
of $B$, there are at least $\|B_{2}{\|}\cdot N/(4M)$ 0s in $B_{2}$. On the
other hand, the number of 0s in $B_{1}$ (resp. $B_{2}$) is bounded by $r$, and
therefore $\|B_{V}[i,r]{\|}=\|B_{1}{\|}+\|B_{2}{\|}\leq 4r\cdot M/N+4r\cdot
M/N\leq 8r\cdot 4M/N$.

It remains to show that the algorithm can be implemented efficiently. In
addition to the linked list $L_{1}$ representing the runs of 1s in $V$, the
algorithm maintains a linked list $L_{2}$ of the intervals of marked 0s,
sorted by their left endpoints. The algorithm simulates marking the 0s for all
1s in the current run at once, taking $\mathcal{O}(R)$ time in total. Having
computed $L_{2}$, the algorithm scans $L_{1}$ and $L_{2}$ in parallel to
extract the set $U$, which takes $\mathcal{O}(R)$ time as well, thus
completing the proof.

######  Corollary 2.5.

Consider a string
$P\in\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>containing $D$ wildcards arranged in $G$ groups. If $D<m/4$, then there is a
fragment $S$ of $P$ of length $L=\lfloor m/(8G)\rfloor$ whose every position
is a sparsifier, and one can compute $S$ in $\mathcal{O}(G)$ time.

######  Proof 2.6.

An application of Lemma 2.3 to $P$ with wildcards treated as 1s and solid
characters treated as 0s returns $m/2-D>m/4$ sparsifiers in the form of $G+1$
intervals in $\mathcal{O}(G)$ time. Thus, there is a fragment of size at least
$m/(4(G+1))\geq L$ whose every position is a sparsifier; the $L$-length prefix
of this fragment satisfies the condition of the claim.

##  3 Exact Pattern Matching in the PILLAR Model

In this section, we consider a pattern $P$ of length $m$ with $D\geq 1$
wildcards arranged in $G$ groups and a solid text $T$ of length $n$ such that
$n\leq 3m/2$. We then use the “standard trick” presented in the introduction
to lift the result to texts of arbitrary length. We prove a structural result
for the exact occurrences of $P$ in $T$ and show how to compute them
efficiently when the product of $D$ and $G$ is small. In particular, we
compute them in linear time when $DG=\mathcal{O}(m)$, thus improving by a
logarithmic factor over the state-of-the-art $\mathcal{O}(n\log m)$-time
algorithms in this case.

######  Definition 3.1 (Misperiods).

Consider a string $V$ over alphabet
$\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>We say that a position $x$ is a misperiod with respect to a solid fragment
$V[i\mathinner{.\,.}j]$ when $V[x]$ does not match $V[y]$, where $y$ is any
position in $[i\mathinner{.\,.}j]$ such that
$\textsf{per}(V[i\mathinner{.\,.}j])$ divides $|y-x|$. Additionally, we
consider positions $0$ and $|V|+1$ as misperiods. We denote the set of the at
most $k$ rightmost misperiods smaller than $i$ with respect to
$V[i\mathinner{.\,.}j]$ by $\mathsf{LeftMisper}(V,i,j,k)$. Similarly, we
denote the set of the at most $k$ leftmost misperiods larger than $j$ with
respect to $V[i\mathinner{.\,.}j]$ by $\mathsf{RightMisper}(V,i,j,k)$.

######  Example 3.2.

Consider string
$V=\texttt{cc\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color@gray@fill{0.9}$\blacklozenge$}}}bd\text@underline{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{abcabcab}}cab}$.
The misperiods with respect to the underlined and highlighted fragment
$V[6\mathinner{.\,.}13]$, which has period $3$, are positions $0$, $1$, $5$,
and $|V|+1=17$. We have $\mathsf{LeftMisper}(V,6,13,2)=\\{1,5\\}$ and
$\mathsf{RightMisper}(V,6,13,2)=\\{17\\}$.

The next lemma states that the sets $\mathsf{LeftMisper}(V,i,j,k)$ and
$\mathsf{RightMisper}(V,i,j,k)$ can be computed efficiently in an incremental
fashion. Its proof, which can be found in Appendix B, uses the kangaroo method
and closely follows [7, 11].

######  Lemma 3.3.

Consider a string $V$ over an alphabet
$\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>and a solid periodic fragment $V[i\mathinner{.\,.}j]$ of $V$. The elements of
either of $\mathsf{LeftMisper}(V,i,j,|V|)$ and
$\mathsf{RightMisper}(V,i,j,|V|)$ can be computed in the increasing order with
respect to their distance from position $i$ so that:

  * •

the first misperiod $x$ can be computed in $\mathcal{O}(1+G_{0})$ time in the
PILLAR model, where $G_{0}$ denotes the number of groups of wildcards between
positions $x$ and $i$;

  * •

given the $t$-th misperiod $x\not\in\\{0,|V|+1\\}$, the $(t+1)$-th misperiod
can be computed in $\mathcal{O}(1+G_{t})$ time in the PILLAR model, where
$G_{t}$ denotes the number of groups of wildcards between said misperiods.

A direct application of the above lemma yields the following fact.

######  Corollary 3.4.

For any integer $k$, the sets $\mathsf{LeftMisper}(V,i,j,k)$ and
$\mathsf{RightMisper}(V,i,j,k)$ can be computed in $\mathcal{O}(k+G)$ time in
the PILLAR model.

######  Definition 3.5.

For two strings $S$ and $Q$, let $\mathsf{MI}(S,Q)$ denote the set of
positions of mismatches between $S$ and $Q^{\infty}$.

######  Definition 3.6 ($S$-runs).

A fragment of a solid string $V$ spanned by a set of occurrences of a solid
string $S$ in $V$ whose starting positions form an inclusion-maximal
arithmetic progression with difference $\textsf{per}(S)$ is called an $S$-run.

######  Example 3.7.

Let
$V=\texttt{cab\text@underline{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{abcabcabcab}}c}$
and $S=\texttt{abcab}$. The underlined and highlighted fragment
$V[4\mathinner{.\,.}14]$ is the sole $S$-run in $V$; it is spanned by the
occurrences of $S$ at positions $4$, $7$, and $10$.

The following fact characterises the overlaps of $S$-runs; its proof is
deferred to Appendix B.

######  Fact 4.

Two $S$-runs can overlap by no more than $\textsf{per}(S)-1$ positions.

We need a final ingredient before we prove the main theorem of this section.
We state a more general variant of the statement than we need here that also
accounts for $k$ mismatches, as this will come handy in the subsequent
section. For the purposes of this section one can think of $k$ as $0$. The
following corollary follows from [12, Lemma 4.6] via the reduction to
computing $(D+k)$-mismatch occurrences of $P_{\\#}$ in $T$.

######  Corollary 3.8 (of [12, Lemma 4.6]).

Let $S$ be a string with $D$ wildcards, let $T$ be a solid string such that
$|T|\leq 3|S|/2$, let $k\in[0\mathinner{.\,.}m]$ and $d\geq 2(D+k)$ be a
positive integer, and let $Q$ be a primitive solid string such that $|Q|\leq
m/8d$ and $\delta_{H}(S,Q^{\infty})\leq d$. Then, we can compute, in
$\mathcal{O}(d)$ time in the PILLAR model, a fragment
$T^{\prime}=T[\ell\mathinner{.\,.}r]$ of $T$ such that

  * •

$\delta_{H}(T^{\prime},Q^{\infty})\leq 3d$, and

  * •

all elements of
$\mathrm{Occ}_{k}(P,T^{\prime})=\\{p-\ell:p\in\mathrm{Occ}_{k}(P,T)\\}$ are
equivalent to $0\pmod{|Q|}$.

######  Theorem 3.9.

Consider a pattern $P$ of length $m$ with $D$ wildcards arranged in $G$ groups
and a solid text $T$ of length $n\leq 3m/2$. Either $P$ has $\mathcal{O}(D)$
occurrences in $T$ or $P$ has a deterministic period $q=\mathcal{O}(m/D)$. A
representation of the occurrences of $P$ in $T$ as $\mathcal{O}(DG)$
arithmetic progressions with common difference $q$ can be computed in
$\mathcal{O}(DG\log\log D)$ time plus the time required to perform
$\mathcal{O}(DG)$ PILLAR operations.

######  Proof 3.10.

First, observe that if $D=\Theta(m)$ the statement holds trivially as there
can only be $\mathcal{O}(m)$ occurrences and we can compute them using
$\mathcal{O}(mG)$ PILLAR operations, e.g., by applying 3 for each position of
the text. We thus henceforth assume that $D<m/4$.

We apply Corollary 2.5 to $P$, thus obtaining, in $\mathcal{O}(G)$ time, a
fragment $S=P[x\mathinner{.\,.}y]$ of length $m/(8G)$ whose every position is
a sparsifier. (As an implication, $S$ is a solid fragment.) Then, we compute
all occurrences of $S$ in $T$ in $\mathcal{O}(G)$ time in the PILLAR model,
represented as $\mathcal{O}(G)$ arithmetic progressions with common difference
$\textsf{per}(S)$ (see Corollary 2.1).

##### Case (i@): $S$ has less than $384D$ occurrences in $T$.

In this case, we try to extend each such occurrence to an occurrence of $P$ in
$T$ using 3 in $\mathcal{O}(G)$ time in the PILLAR model. This takes
$\mathcal{O}(DG)$ time in total in the PILLAR model.

##### Case (ii@): $S$ has at least $384D$ occurrences in $T$.

In this case, we have two occurrences of $S$ in $T$ starting within
$(3m/2)/(384D)$ positions of each other, and hence $\textsf{per}(S)\leq
m/(256D)$. Let $Q=S[1\mathinner{.\,.}\textsf{per}(S)]$. By definition of
$\textsf{per}(S)$, $S$ is a prefix of $Q^{\infty}$ and by 1, $Q$ is primitive.
Using Corollary 3.4, we compute the sets $\mathsf{LeftMisper}(P,x,y,1)$ and
$\mathsf{RightMisper}(P,x,y,1)$ in $\mathcal{O}(G)$ time in the PILLAR model.
In other words, we compute the maximal fragment $V$ of $P$ that contains $S$
and matches exactly some substring of $Q^{\infty}$.

##### Subcase (a): $V=P$.

We conclude that $q=\mathcal{O}(m/D)$ is a deterministic period of $P$. We
replace $Q$ by its (possibly trivial) rotation $Q_{0}$ such that $P$ is equal
to a prefix of $Q_{0}^{\infty}$ and then apply Corollary 3.8 to compute, in
$\mathcal{O}(D)$ time in the PILLAR model, a fragment $T^{\prime}$ of $T$ that
contains the same number of occurrences of $P$ as $T$, is at Hamming distance
$\mathcal{O}(D)$ from a prefix of $Q^{\infty}$, and only has occurrences of
$P$ at positions equivalent to $1\pmod{q}$.

It now suffices to show how to compute the occurrences of $P$ in $T^{\prime}$.
As in previous works [7, 12], we take a sliding window approach. In addition,
let $W$ be the set of positions in $P$ where we have a wildcard. For
$i\in[1\mathinner{.\,.}|T^{\prime}|-m+1]$, define $\textsf{Hidden}(i)$ to be
the size of the intersection of
$\mathsf{MI}(T^{\prime},Q)\cap[i\mathinner{.\,.}i+m)$ with $i+W$.333For a set
$Y$ and an integer $z$, by $z+Y$ we denote the set $\\{z+y:y\in Y\\}$.
Intuitively, this is the number of mismatches between
$T^{\prime}[i\mathinner{.\,.}i+m)$ and $Q^{\infty}$ that are aligned with a
wildcard in $P$ (and are hence “hidden”) when we align $P$ with
$T^{\prime}[i\mathinner{.\,.}i+m)$. $\textsf{Hidden}(\cdot)$ is a step
function whose value changes $\mathcal{O}(DG)$ times as we increase $i$, since
each mismatch enters or exits the window $[i\mathinner{.\,.}i+m)$ at most once
and whether it is hidden or not changes at most $2G$ times. We compute
$\textsf{Hidden}(1)$ and store the positions where the function changes (as
well as by how much) as events in the increasing order; this sorting takes
$\mathcal{O}(DG\log\log D)$ time [26].

For a position $i\leq|T^{\prime}|-m+1$, the distance $d_{i}$ between
$T^{\prime}[i\mathinner{.\,.}i+m)$ and $P$ is given by

$d_{i}=\mathsf{MI}(T^{\prime}[i\mathinner{.\,.}i+m),Q)-\textsf{Hidden}(i).$

We maintain this value as we, intuitively, slide $P$ on $T$, $q$ positions at
a time. If there are no events in
$(i\mathinner{.\,.}i+q]\subseteq[1\mathinner{.\,.}|T^{\prime}|]$, then
$d_{i}=d_{i+q}$. This allows us to report all occurrences of $P$ in $T$
efficiently in the form of $\mathcal{O}(DG)$ arithmetic progressions with
common difference $q$ by processing all events in a left-to-right manner in
$\mathcal{O}(DG)$ time.

##### Subcase (b): $V\neq P$.

Now, let us consider the case where $V\neq P$. Our goal is to show that, in
this case, the occurrences of $P$ in $T$ are $\mathcal{O}(D)$ and they can be
computed in time $\mathcal{O}(GD)$. Without loss of generality, assume that
$V$ is not a prefix of $P$. This means that
$\mathsf{LeftMisper}(P,x,y,1)=\\{\mu\\}\neq\\{0\\}$. The occurrences of $S$ in
$T$ give us a collection $\mathcal{S}$ of $\mathcal{O}(G)$ $S$-runs in $T$,
any two of which can overlap by less than $\textsf{per}(S)=q$ positions due to
4. For each $S$-run $R$, extend $R$ position by position to the left until
either of the following two conditions is satisfied:

  1. (a)

the ratio of encountered misperiods to the sum of $|R|$ and the number of
prepended positions exceeds $20D/m$,

  2. (b)

the beginning of $T$ has been reached.

Denote by $E_{R}$ the resulting fragment of $T$ (note that $E_{R}$ includes
$R$) and $\mathcal{M}_{R}$ the set of misperiods in it.

The following two claims are of crucial importance for the algorithm’s
performance.

######  Claim 5.

If $p+1$ is an occurrence of $P$ in $T$ that aligns $S$ with an occurrence of
$S$ in an $S$-run $R$, then $p+\mu\in\mathcal{M}_{R}$.

Let $R=T[r\mathinner{.\,.}r^{\prime}]$. We first show that
$p+\mu\in\mathsf{LeftMisper}(T,r,r^{\prime},|T|)$. We have that $P[\mu]$,
which is a solid character, is different from a character $P[\pi]$, where
$\pi\in[x\mathinner{.\,.}y]$ and $\pi-\mu\equiv 0\pmod{q}$. Further,
$P[\pi]=T[p+\pi]$, where $p+\pi\in[r\mathinner{.\,.}r^{\prime}]$, and
$P[\mu]=T[p+\mu]$. This means that $T[p+\mu]=P[\mu]\neq P[\pi]=T[p+\pi]$. Now,
since $(p+\pi)-(p+\mu)=\pi-\mu$ is divisible by $q$, which is the period of
$T[r\mathinner{.\,.}r^{\prime}]$, we have
$p+\mu\in\mathsf{LeftMisper}(T,r,r^{\prime},|T|)$. See Figure 1.

Now, assume for sake of a contradiction that $p+\mu\not\in\mathcal{M}_{R}$.
Intuitively, this can only be the case if the extension of $R$ did not reach
the beginning of $T$ due to encountering too many misperiods. On the other
hand, the fragment $P[\mu\mathinner{.\,.}x)S$ of $P$ contains only one
misperiod and cannot contain many wildcards, since every position of $S$ is a
sparsifier. As a result, a misperiod in $T$ will be aligned with a “regular”
position of $P$, contradicting the fact that $p+1$ is an occurrence of $P$ in
$T$. Formally, let $p+\nu>p+\mu$ be the misperiod that forced the extension
algorithm to stop, i.e. $E_{R}=T[p+\nu\mathinner{.\,.}r^{\prime}]$. (See
Figure 1.) Then, the stopping condition implies that
$|\mathcal{M}_{R}|>|E_{R}|\cdot 20D/m$. All these misperiods belong to the
prefix of $E_{R}$ matching $P[\nu\mathinner{.\,.}y]$. On the other hand, due
to $\mu<\nu$, we have
$[\nu\mathinner{.\,.}y]\cap\mathsf{LeftMisper}(P,x,y,|P|)=\emptyset$.
Furthermore, every position of $S$ is a sparsifier, and therefore the number
of wildcards in $P[\nu\mathinner{.\,.}y]$ is at most $|E_{R}|\cdot 16D/m$.
Thus, there exists $p+s\in\mathcal{M}_{R}$ such that
$s\not\in\mathsf{LeftMisper}(P,x,y,|P|)$ and $P[s]$ is not a wildcard. This
implies that $T[p+s]\neq P[s]$, a contradiction to the fact that $p+1$ is an
occurrence of $P$.

$T$$p+1$$p+\mu$$p+\nu$$r$$p+\pi$$r^{\prime}$$R$$E_{R}$$\textsf{per}(S)$$S$$S$$S$$P$$\mu$$\nu$$x$$\pi$$y$$S$$\textsf{per}(S)$no
misperiods$\leq|E_{R}|\cdot 16D/m$ wildcards Figure 1: The run $R$ and an
occurrence $p$ of $P$ in $T$ that aligns $S$ with an occurrence of $S$ in $R$.

######  Claim 6.

The set $\cup_{R\in\mathcal{S}}\mathcal{M}_{R}$ is of size $\mathcal{O}(D)$
and it can be computed using $\mathcal{O}(D)$ PILLAR operations given the set
$\mathcal{S}$ of $S$-runs and $q$.

We start by initialising a set $\mathcal{R}:=\mathcal{S}$, marking every
element of $\mathcal{R}$ as unprocessed and a set $\mathcal{M}=\emptyset$. We
then iteratively perform the following procedure for the rightmost unprocessed
$R\in\mathcal{R}$. Compute $\mathcal{M}_{R}$ using Lemma 3.3, set
$\mathcal{M}:=\mathcal{M}\cup\mathcal{M}_{R}$, and mark $R$ as processed. This
takes time proportional to the sum of $|\mathcal{M}_{R}|$ and the number of
groups of wildcards contained in $E_{R}$. During the procedure, whenever we
extend beyond any (unprocessed) $S$-run, we remove it from $\mathcal{R}$—the
total time required for this step is $\mathcal{O}(G)$.

We now show the correctness of the algorithm. As
$Q=S[1\mathinner{.\,.}\textsf{per}(S)]$ is primitive (1), it cannot match any
of its rotations. By 4, any two $S$-runs overlap by less than $q$ positions.
Therefore, if, while extending a run
$R=T[r\mathinner{.\,.}r^{\prime}]\in\mathcal{R}$, we extend beyond a run
$R^{\prime}=T[t\mathinner{.\,.}t^{\prime}]\in\mathcal{R}$, we have that $q$
divides $r-t$, since otherwise we would accumulate at least

$\lfloor(|R^{\prime}|-q)/q\rfloor\geq|S|/q-2\geq\frac{m/(8G)}{m/(256D)}-2\geq
30D=(3/2)\cdot 20D$

misperiods and we would have thus breached the threshold as the length of the
extension $E_{R}$ is at most $3m/2$. This implies that
$\mathcal{M}_{R^{\prime}}\subseteq\mathcal{M}_{R}$ and hence the algorithm
correctly computes $\mathcal{M}=\cup_{R\in\mathcal{S}}\mathcal{M}_{R}$.

Finally, we analyse the algorithm’s time complexity. The run extensions take
$\mathcal{O}(|\mathcal{M}|+G)$ time in total in the PILLAR model since each
group of wildcards is contained in $E_{R}$ for at most one $R\in\mathcal{R}$.
Since the above analysis implies that each position of the text belongs to
$\mathcal{O}(1)$ fragments $E_{R}$ for $R\in\mathcal{R}$,

$|\mathcal{M}|\leq\sum_{R\in\mathcal{R}}|\mathcal{M}_{R}|\leq|\mathcal{R}|+\sum_{R\in\mathcal{R}}|E_{R}|\cdot
20D/m\leq\mathcal{O}(G)+3\cdot(3m/2)\cdot 20D/m=\mathcal{O}(D).$

Consequently, the algorithm takes $\mathcal{O}(G+D)=\mathcal{O}(D)$ time.

We can now conclude the proof of the theorem. By 5, the starting positions of
occurrences of $P$ in $T$ are in the set $\\{\nu-\mu+1:\nu\in\mathcal{M}\\}$.
This concludes the proof of the combinatorial bound, as the size of this set
is $\mathcal{O}(D)$. As for the time complexity, we verify each such candidate
position in $\mathcal{O}(G)$ time using 3. In total, this takes time
$\mathcal{O}(DG)$ in the PILLAR model.

##  4 Pattern Matching with $k$ Mismatches in the PILLAR Model

In this section, we extend the results of Section 3, showing that the
$k$-mismatch occurrences of a pattern
$P\in\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>in a solid text $T$ can be computed in $\tilde{\mathcal{O}}((D+G)\cdot(G+k))$
time in the PILLAR model. Further, we prove that the starting positions of
these occurrences can be decomposed into $\mathcal{O}((D+k)G)$ arithmetic
progressions with the same difference, plus $\mathcal{O}((D+k)k)$ additional
$k$-mismatch occurrences.

See 1.2

###  4.1 Computing Structure in the Pattern

We start by showing a _decomposition lemma_ , that either extracts useful
structure from the pattern or reveals that it is close to a periodic string.
Our lemma is analogous to the decomposition lemma for the case where both
strings are solid [12, Lemma 3.6]. The crucial differences are two:

  * •

in Case I, we require that breaks are solid strings,

  * •

in Case II, we ensure that each computed repetitive region contains a
sparsifier.

######  Lemma 4.1.

Let $P$ be a string of length $m$ that contains $D\leq m/16$ wildcards
arranged in $G$ groups. Further, let $k\in[1\mathinner{.\,.}m]$ be an integer
threshold, and let $\gamma:=G+k$ and $\tau:=D+k$. At least one of the
following holds:

  1. (I)

$P$ contains $2\gamma$ disjoint solid strings $B_{1},\ldots,B_{2\gamma}$, that
we call _breaks_ , each having length $m/(16\gamma)$ and the period greater
than $m/(512\tau)$.

  2. (II)

$P$ contains $r$ disjoint _repetitive regions_ $R_{1},\ldots,R_{r}$ of total
length $m_{R}\geq m/8$, such that, for every $i$:

     * •

$R_{i}$ contains a sparsifier,

     * •

$|R_{i}|\geq m/16\gamma$, and,

     * •

for a primitive string $Q_{i}$ with $|Q_{i}|\leq m/(512\tau)$, we have
$\delta_{H}(R_{i},Q_{i}^{\infty})=\lceil 32k/m\cdot|R_{i}|\rceil$.

  3. (III)

There exists a primitive string $Q$ of length at most $m/(512\tau)$ such that
$\delta_{H}(P,Q^{\infty})\leq 32k$.

Moreover, there is an algorithm that takes $\mathcal{O}(G+k)$ time in the
PILLAR model and distinguishes between the above cases, returning one of the
following: either $2\gamma$ disjoint breaks, or repetitive regions
$R_{1},\ldots,R_{r}$ of total length at least $m/8$ along with primitive
strings $Q_{1},\ldots,Q_{r}$, or a primitive string $Q$ along with
$\mathsf{MI}(P,Q)$.

######  Proof 4.2.

We process $P$ from left to right. While we have not yet arrived to one of the
Cases I-III, we repeat the following procedure. We take the leftmost fragment
$F$ of $P$ of length $m/(16\gamma)$ that starts to the right of the current
position $j$ and consists only of sparsfiers. If the period of $F$ is greater
than $m/(512\tau)$, then we add $F$ to the set of breaks and proceed to
position $j+|F|$. Otherwise, we extend $F$ to the right until the either
number of mismatches between $F$ and $Q^{\infty}$, where
$Q:=F[1\mathinner{.\,.}\textsf{per}(F)]$, becomes equal to
$\lceil{32k/m\cdot|F|\rceil}$ or we reach the end of $P$. In the former case,
we add $F$ to the set of repetitive regions and proceed to position $j+|F|$.
In the latter case, we extend $F$ to the left until either the number of
mismatches between $F$ and $Q^{\prime\infty}$, where
$Q^{\prime}=\textsf{rot}^{|F|-m+j}(Q)$, becomes equal to
$\lceil{32k/m\cdot|F|\rceil}$, or we reach the start of $P$. If we accumulate
enough mismatches, we update the set of repetitive regions to be $\\{F\\}$ and
terminate the algorithm. Otherwise, i.e., if we reach the start of $P$, we
conclude that $P$ is at Hamming distance at most $32k$ from a solid string
with period at most $m/(512\tau)$, and we are hence in Case III.

Let us now prove the correctness of the above algorithm. We first show that if
the algorithm has not already concluded that we are in one of the three cases,
then there exists a fragment $F$ of sparsifiers that starts in
$[j\mathinner{.\,.}7m/8]$, where $j$ is our current position. A direct
application of Lemma 2.3 implies that there are at least $m/2-D-m/8\geq 5m/16$
sparsifiers in $[1\mathinner{.\,.}7m/8]$ (since $D\leq m/16$), and they are
arranged in $G+1$ intervals. By construction, the sparsifiers in an interval
are covered from left to right, and hence at most $m/16\gamma-1$ positions can
be left uncovered in each interval. Under our assumptions, the breaks and
repetitive regions that have been already computed cover less than
$2\gamma\cdot m/(16\gamma)+m/8=m/4$ positions. If there is no fragment $F$ of
length $m/16\gamma$ that consists only of sparsifiers and starts in
$[j\mathinner{.\,.}7m/8]$, then at least

$5m/16-(m/16\gamma-1)\cdot(G+1)>5m/16-(m/16\gamma)\cdot(G+1)\geq m/4$

of the sparsifiers have been already covered, a contradiction. From the above,
it also follows that if a fragment $F$ reaches the end of the pattern during
its extension, then its length becomes at least $m/8$. Then, if such a
fragment is extended to the left and accumulates enough mismatches with
respect to the periodicity before the start of $P$ is reached, we can set our
set of repetitive regions to $\\{F\\}$ and terminate the algorithm. This
completes the proof of the correctness of the structural result.

Now, note that the presented proof is algorithmic. Lemma 2.3 computes the set
of sparsifiers, represented as $\mathcal{O}(G)$ disjoint intervals, in
$\mathcal{O}(G)$ time. After this preprocessing, the procedure can retrieve a
new fragment $F$ in constant time. In total, it considers $\mathcal{O}(G)$
fragments. Computing the period of a solid string takes $\mathcal{O}(1)$ time
in the PILLAR model [12, 34]. Moreover, in our attempt to accumulate
$\mathcal{O}(k)$ misperiods in total, we encounter each group of wildcards at
most twice: at most once when extending to the right and at most once when
extending to the left. All such extensions thus take $\mathcal{O}(G+k)$ time
in the PILLAR model due to Lemma 3.3.

###  4.2 The Almost Periodic Case

Case III is treated quite similarly to Case ii@(a) of the exact pattern
matching algorithm (see Section 3).

######  Lemma 4.3.

Let $S$ be a pattern of length $m$ with $D$ wildcards arranged in $G$
groups444In the final algorithm, $S$ is a fragment of the pattern $P$,
potentially much shorter than the text., let $T$ be a solid text of length
$n$, let $k\in[0\mathinner{.\,.}m]$, and let $d\geq 2(k+D)$ be a positive
integer. If there exists a primitive string $Q$ with $|Q|\leq m/8d$ such that
$\delta_{H}(S,Q^{\infty})\leq\min\\{d,4k\\}$, then we can compute a
representation of $\mathrm{Occ}_{k}(S,T)$ as $\mathcal{O}(d(G+k))$ arithmetic
progressions with common difference $|Q|$ in $\mathcal{O}(d(G+k)\log\log
d\cdot n/m)$ time plus $\mathcal{O}(d\cdot n/m)$ PILLAR operations. Moreover,
if $\delta_{H}(S,Q^{\infty})\geq 2k$, then
$|\mathrm{Occ}_{k}(S,T)|=\mathcal{O}(d\cdot n/m)$.

######  Proof 4.4.

We only consider the case when $n\leq 3m/2$. The result then follows using the
“standard trick” presented in the introduction.

We use an event-driven scheme that extends the one used in the almost periodic
case of Section 3. First, we apply Corollary 3.8 to compute a fragment
$T^{\prime}$ of $T$ that contains the same number of $k$-mismatch occurrences
as $T$, is at Hamming distance $\mathcal{O}(d)$ from a prefix of $Q^{\infty}$,
and only has occurrences of $P$ at positions that are equivalent to
$1\pmod{|Q|}$. This takes $\mathcal{O}(d)$ time in the PILLAR model. We then
apply 2 to compute $\mathsf{MI}(T^{\prime},Q)$ in $\mathcal{O}(d)$ time in the
PILLAR model. For a position $i\leq|T^{\prime}|-m+1$, the distance $d_{i}$
between $T^{\prime}[i\mathinner{.\,.}i+m)$ and $S$ is given by

$d_{i}=|\mathsf{MI}(S,Q)|+|\mathsf{MI}(T^{\prime}[i\mathinner{.\,.}i+m),Q)|-2\textsf{Matching}(i)-\textsf{Aligned}(i)-\textsf{Hidden}(i),\text{
where}$

  * •

$\textsf{Matching}(i)$ is the number of positions that are mismatches between
$S$ and $Q^{\infty}$, and $Q^{\infty}$ and $T^{\prime}$, but not between $S$
and $T$, i.e.,

$\textsf{Matching}(i)=|\\{j:j\in\mathsf{MI}(S,Q)\cap\mathsf{MI}(T^{\prime}[i\mathinner{.\,.}i+m),Q)\land
S[j]=T^{\prime}[i+j]\land
S[j]\neq\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>
  * •

$\textsf{Aligned}(i)$ is the number of positions that are mismatches between
$S$ and $Q^{\infty}$, $Q^{\infty}$ and $T^{\prime}$, and $S$ and $T$ (as
opposed to $\textsf{Matching}(i)$), i.e.,

$\textsf{Aligned}(i)=|\\{j:j\in\mathsf{MI}(S,Q)\cap\mathsf{MI}(T^{\prime}[i\mathinner{.\,.}i+m),Q)\land
S[j]\neq T^{\prime}[i+j]\land
S[j]\neq\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>
  * •

$\textsf{Hidden}(i)$ is the number of positions that are mismatches between
$T^{\prime}$ and $Q^{\infty}$, and that are aligned with wildcards, i.e.,

$\textsf{Hidden}(i)=|\\{j:j\in\mathsf{MI}(T^{\prime}[i\mathinner{.\,.}i+m),Q)\land
S[j]=\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>
Recall that every $j\in\mathrm{Occ}_{k}(S,T^{\prime})$ satisfies $j\equiv
1\pmod{|Q|}$ (Theorem 1.1), hence we only consider the values of $d_{i}$ as
$i$ increases by multiples of $|Q|$. Then, the value $d_{i}$ only changes when
one of the following events occurs: a position in $\mathsf{MI}(T^{\prime},Q)$
enters or exits the active window $T^{\prime}[i\mathinner{.\,.}i+m)$, starts
or stops being aligned with a group of wildcards, or starts or stops being
aligned with a position in $\mathsf{MI}(S,Q)$. As
$|\mathsf{MI}(T^{\prime},Q)|=\mathcal{O}(d)$, there are $G$ groups of
wildcards in $S$ and $|\mathsf{MI}(S,Q)|=\mathcal{O}(k)$, there are
$\mathcal{O}(d(G+k))$ events.

If $d_{i}\leq k$, then all positions equivalent to $1\pmod{|Q|}$ until the
subsequent event are $k$-mismatch occurrences, and form an arithmetic
progression with difference $|Q|$. As there are $\mathcal{O}(d(G+k))$ events,
we obtain the stated bound on the number of arithmetic progressions.

We sort the events by index in $\mathcal{O}(d(G+k)\log\log d)$ time [26].
Then, we process them from left to right; processing one event takes constant
time. The initial value of $d_{0}$ can be computed in time linear in the
number of events. Overall, the running time is dominated by the sorting
operation. We additionally perform $\mathcal{O}(d)$ PILLAR operations to
compute $T^{\prime}$.

Finally, if $\delta_{H}(S,Q^{\infty})\geq 2k$, then in any $k$-mismatch
occurrence of $S$ in $T$, at least $2k-k=k$ positions in $\mathsf{MI}(S,Q)$
are aligned with positions in $\mathsf{MI}(T^{\prime},Q)$, as otherwise there
would be more than $k$ mismatches. As we have
$|\mathsf{MI}(S,Q)|=\delta_{H}(S,Q^{\infty})\geq 2k$ and
$|\mathsf{MI}(T^{\prime},Q)|=\mathcal{O}(d)$, there are $\mathcal{O}(dk)$ ways
of aligning misperiods. We thus have
$|\mathrm{Occ}_{k}(S,T)|=\mathcal{O}(dk/k)=\mathcal{O}(d)$ $k$-mismatch
occurrences.

###  4.3 The Remaining Cases

We now show that in each of the Cases I and II of Lemma 4.1, $T$ contains
$\mathcal{O}(D+k)$ $k$-mismatch occurrences of $P$, and we can efficiently
compute a set $\mathcal{S}$ of $\mathcal{O}(D+k)$ positions that contains all
the starting positions of $k$-mismatch occurrences of $P$. We then verify each
of the candidate positions in $\mathcal{S}$ in $\mathcal{O}(G+k)$ time using
3.

We first handle the case when the pattern contains $2\gamma$ disjoint breaks.

######  Lemma 4.5.

In Case I of Lemma 4.1, a solid text $T$ of length at most $3m/2$ contains
$\mathcal{O}(D+k)$ $k$-mismatch occurrences of $P$. Moreover, we can compute
in $\mathcal{O}((D+k)(G+k))$ time in the PILLAR model a set
$\mathcal{S}\supseteq\mathrm{Occ}_{k}(P,T)$ of size $\mathcal{O}(D+k)$.

######  Proof 4.6.

Let $\\{B_{i}\\}$ be the breaks computed by the algorithm of Lemma 4.1. For
every $i$, let $p_{i}$ denote the starting position of $B_{i}$ in $P$. For
every exact occurrence $j$ of $B_{i}$ in $T$, we put a mark at position
$j-p_{i}+1$ in $T$. As $B_{i}$ has period greater than $m/512\tau$, $T$
contains at most $768\tau$ occurrences of $B_{i}$, and they can be computed in
$\mathcal{O}(|T|/|B_{i}|+\tau)=\mathcal{O}(\gamma+\tau)=\mathcal{O}(D+k)$ time
in the PILLAR model. As there are $2\gamma$ breaks, we place at most
$768\tau\cdot 2\gamma=1536\tau\gamma$ marks in total.

Now, in every occurrence of $P$, at most $k$ of the $B_{i}$s are not matched
exactly and hence at least $2\gamma-k$ of the $B_{i}$s are matched exactly.
Thus, every position $j\in\mathrm{Occ}_{k}(P,T)$ has at least
$2\gamma-k\geq\gamma$ marks. We designate $\mathcal{S}$ to be the set of
positions with at least $2\gamma-k$ marks. Observe that
$\mathrm{Occ}_{k}(P,T)\subseteq\mathcal{S}$ and $|\mathcal{S}|\leq
1536\tau\gamma/(2\gamma-k)\leq 1536\tau=\mathcal{O}(D+k)$. Thus, $\mathcal{S}$
satisfies the conditions of the lemma’s statement.

We obtain a similar result for repetitive regions via a more sophisticated
marking scheme.

######  Lemma 4.7.

In Case II of Lemma 4.1, given a solid text $T$ of length at most $3m/2$, we
can compute in $\mathcal{O}((D+k)(G+k)\log\log(D+k))$ time plus
$\mathcal{O}((D+k)(G+k))$ PILLAR operations a set
$\mathcal{S}\supseteq\mathrm{Occ}_{k}(P,T)$ of size $\mathcal{O}(D+k)$.

######  Proof 4.8.

Let $\\{R_{i}\\}$ be the repetitive regions computed by the algorithm of Lemma
4.1. For every $i$, let $D_{i}$ denote the number of wildcards in $R_{i}$,
$d_{i}=\lceil 32(k+D)/m\cdot|R_{i}|\rceil$, and $k_{i}=\lfloor
16k/m\cdot|R_{i}|\rfloor$. For every $i$ and every $k_{i}$-mismatch occurrence
of $R_{i}$, we put a mark of weight $|R_{i}|$ at the corresponding starting
position for $P$.

######  Claim 7.

For every $i$, there are $\mathcal{O}(D+k)$ $k_{i}$-mismatch occurrences of
$R_{i}$ in $T$. Moreover, the total weight of marks is $\mathcal{O}((D+k)\cdot
m_{R})$.

We apply Lemma 4.3 to each repetitive region. First, let us show that the
conditions of the lemma are satisfied. Recall that $|R_{i}|\geq m/(16(G+k))$
and hence $16k/m\cdot|R_{i}|\geq 1$.

  * •

$d_{i}\geq 2(k_{i}+D_{i})$: As $R_{i}$ contains a sparsifier, we have
$D_{i}\leq 16D/m\cdot|R_{i}|$ and hence the bound follows.

  * •

$|Q_{i}|\leq|R_{i}|/8d_{i}$: We have $d_{i}\leq
64|R_{i}|(k+D)/m\Longleftrightarrow m\leq 64|R_{i}|(k+D)/d_{i}$ and hence

$|Q_{i}|\leq m/(512\tau)=m/(512(k+D))\leq
64|R_{i}|/(512d_{i})=|R_{i}|/(8d_{i}).$

  * •

$\delta_{H}(R_{i},Q_{i}^{\infty})\leq\min\\{d_{i},4k_{i}\\}$: This follows
from the fact that $\delta_{H}(R_{i},Q_{i}^{\infty})=\lceil
32k/m\cdot|R_{i}|\rceil$.

Now, since $\delta_{H}(R_{i},Q_{i}^{\infty})\geq 2k_{i}$, $T$ contains
$\mathcal{O}(d_{i}n/|R_{i}|)$ occurrences of $R_{i}$. Hence, the total weight
of marks for a given $R_{i}$ is

$w_{i}=\mathcal{O}(d_{i}n/|R_{i}|)\cdot|R_{i}|=\mathcal{O}((D+k)\cdot|R_{i}|),$

since $m=\Theta(n)$, and, summing over $i=1,\ldots,r\leq 2\gamma$, we get that
the total weight of marks that we place is $\mathcal{O}((D+k)\cdot m_{R})$.

We next lower bound the number of marks placed at a $k$-mismatch occurrence of
$P$.

######  Claim 8.

The total weight of marks placed in any position
$\ell\in\mathrm{Occ}_{k}(P,T)$ is at least $m_{R}-m/16$.

Consider a $k$-mismatch occurrence of $P$ at position $\ell$ of $T$. For every
$i$, let $r_{i}$ be the starting position of $R_{i}$ in $P$, and let
$k_{i}^{\prime}=\delta_{H}(R_{i},T[\ell+r_{i}\mathinner{.\,.}\ell+r_{i}+|R_{i}|))$
be the Hamming distance between $R_{i}$ and the fragment of $T$ with which it
is aligned. As $\ell\in\mathrm{Occ}_{k}(P,T)$ and the $R_{i}$s are disjoint,
we have $\sum_{i}k_{i}^{\prime}\leq k$. Now, let $I:=\\{i:k_{i}^{\prime}\leq
k_{i}\\}$. We have

$\sum_{i\notin I}|R_{i}|=\sum_{i\notin
I}\frac{16mk}{16mk}\cdot|R_{i}|=\frac{m}{16k}\sum_{i\notin
I}\frac{16k}{m}\cdot|R_{i}|<\frac{m}{16k}\sum_{i\notin
I}k_{i}^{\prime}\leq\frac{m}{16k}\sum_{i=1}^{r}k_{i}^{\prime}\leq\frac{m}{16}.$

The total weight of the marks placed at position $\ell$ in $T$ due to $i\in I$
is $|R_{i}|$, which amounts to a total weight of at least $m_{R}-\sum_{i\notin
I}|R_{i}|\geq m_{R}-m/16$.

Therefore, we can choose $\mathcal{S}$ to contain all positions to which we
have placed marks of total weight at least $m_{R}-m/16$. Dividing the total
weight of marks which is $\mathcal{O}((D+k)\cdot m_{R})$ by $m_{R}-m/16$ which
is at least $m_{R}/2$ since $m_{R}\geq m/8$, we obtain
$|\mathcal{S}|=\mathcal{O}(D+k)$.

Finding the $k_{i}$-mismatch occurrences of $R_{i}$ using Lemma 4.3 takes
$\mathcal{O}(d_{i}(G_{i}+k_{i})\log\log d_{i}\cdot
n/|R_{i}|)=\mathcal{O}((D+k)(G_{i}+k_{i})\log\log(D+k))$ time plus
$\mathcal{O}(d_{i}\cdot n/|R_{i}|)=\mathcal{O}(D+k)$ PILLAR operations. As the
$R_{i}$s are disjoint, the sum of the $G_{i}$s is $\mathcal{O}(G)$. Further,
the sum of the $k_{i}$s is $\mathcal{O}(k)$. Thus, summing over all $i$,
computing the occurrences of all $\mathcal{O}(G+k)$ $R_{i}$s takes
$\mathcal{O}((D+k)(G+k)\log\log(D+k))$ time plus $\mathcal{O}((D+k)(G+k))$
PILLAR operations.

Therefore, computing the set $\mathcal{S}$ of possible starting positions of
$P$ in $T$ can be done in $\mathcal{O}((D+k)(G+k)\log\log(D+k))$ time plus
$\mathcal{O}((D+k)(G+k))$ PILLAR operations.

Lemma 4.5 and Lemma 4.7 are the last pieces needed to prove the algorithmic
part of Theorem 1.2.

##### Proof of the algorithmic part of Theorem 1.2.

If $P$ contains $D>m/16$ wildcards, then we apply kangaroo jumping (3) to
check whether each of the $n\leq 3m/2$ positions in $T$ is a $k$-mismatch
occurrence of $P$. This requires $\mathcal{O}(m(G+k))=\mathcal{O}((D+k)(G+k))$
time in the PILLAR model.

Otherwise, we have $D\leq m/16$, and we can run the algorithm of Lemma 4.1,
which takes $\mathcal{O}(G+k)$ time in the PILLAR model. In Cases I and II, we
use Lemma 4.5 and Lemma 4.7, respectively, to compute using
$\mathcal{O}((D+k)(G+k)\log\log(D+k))$ time plus $\mathcal{O}((D+k)(G+k))$
PILLAR operations a set $\mathcal{S}$ of size $\mathcal{O}(D+k)$ that contains
all $k$-mismatch occurrences of $P$. We verify each of these positions using
3, in total time $\mathcal{O}((D+k)(G+k))$ in the PILLAR model. In Case III of
Lemma 4.1, $P$ satisfies the conditions required for $S$ in Lemma 4.3, and we
can apply this lemma to compute $\mathrm{Occ}_{k}(P,T)$ using
$\mathcal{O}((D+k)(G+k)\log\log(D+k))$ time plus $\mathcal{O}(D+k)$ PILLAR
operations.

In total, the algorithm uses $\mathcal{O}((D+k)(G+k)\log\log(D+k))$ time and
$\mathcal{O}((D+k)(G+k))$ PILLAR operations. ∎

##### Proof of the combinatorial part of Theorem 1.2.

Finally, we explain how we can refine the analysis of Lemma 4.3 to obtain a
more precise characterisation of the structure of $k$-mismatch occurrences.

######  Lemma 4.9.

The $k$-mismatch occurrences of $P$ in $T$ can be decomposed into
$\mathcal{O}((D+k)G)$ arithmetic progressions with common difference $q$ and
$\mathcal{O}((D+k)k)$ additional occurrences.

######  Proof 4.10.

We proceed similarly to the proof of Lemma 4.3, with $S=P$. Let $T^{\prime}$
be the fragment of $T$ computed by Corollary 3.8 using $d=\Theta(D+k)$. We
have $|\mathsf{MI}(T^{\prime},Q)|=\mathcal{O}(D+k)$. Define
$d^{\prime}_{i}=|\mathsf{MI}(P,Q)|+|\mathsf{MI}(T^{\prime}[i\mathinner{.\,.}i+m),Q)|-\textsf{Hidden}(i)$,
where
$\textsf{Hidden}(i)=|\\{j:j\in\mathsf{MI}(T^{\prime}[i\mathinner{.\,.}i+m),Q)\land
P[j]=\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>Note that
$\delta_{H}(T^{\prime}[i\mathinner{.\,.}i+m),P)=d^{\prime}_{i}-2\textsf{Matching}(i)-\textsf{Aligned}(i)$,
where

$\displaystyle\textsf{Matching}(i)$
$\displaystyle=\\{j:j\in\mathsf{MI}(P,Q)\cap\mathsf{MI}(T^{\prime}[i\mathinner{.\,.}i+m),Q)\land\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>P[j]=T^{\prime}[i+j]\\},$ $\displaystyle\textsf{Aligned}(i)$
$\displaystyle=\\{j:j\in\mathsf{MI}(P,Q)\cap\mathsf{MI}(T^{\prime}[i\mathinner{.\,.}i+m),Q)\land\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>P[j]\neq T^{\prime}[i+j]\\}$

Therefore, $\delta_{H}(T^{\prime}[i\mathinner{.\,.}i+m),P)\leq
d^{\prime}_{i}$. The inequality is strict if at least one of
$\textsf{Matching}(i)$ or $\textsf{Aligned}(i)$ is positive. In particular,
every position where $d_{i}^{\prime}\leq k$ corresponds to a $k$-mismatch
occurrence of $P$ in $T$. Using the event-driven scheme, we compute the values
$d^{\prime}_{i}$ for all $i\equiv 1\mod|Q|$. The value $d^{\prime}_{i}$ only
changes when a position in $\mathsf{MI}(T^{\prime},Q)$ enters or exits the
active window $T^{\prime}[i\mathinner{.\,.}i+m)$, or when a position in
$\mathsf{MI}(T^{\prime},Q)$ starts or stops being aligned with a group of
wildcards in $P$. Therefore, the values $d^{\prime}_{i}$ change
$\mathcal{O}(G\cdot(D+k))$ times. As we only consider positions $i\equiv
1\mod|Q|$, the set of positions where $d_{i}^{\prime}\leq k$ forms
$\mathcal{O}(G\cdot(D+k))$ arithmetic progressions with common difference
$|Q|$.

This analysis might have missed the $k$-mismatch occurrences where at least
one of $\textsf{Matching}(i),\textsf{Aligned}(i)$ is positive. However, this
requires a misperiod of $P$ to be aligned with a misperiod of $T^{\prime}$.
There are $\mathcal{O}(k)$ of the former and $\mathcal{O}(D+k)$ of the latter,
hence the number of such occurrences is $\mathcal{O}((D+k)k)$.

##  5 A Lower Bound on the Number of Arithmetic Progressions

In this section we show a lower bound on the number of arithmetic progressions
covering the set of $k$-mismatch occurrences of a pattern in a text.

######  Theorem 5.1.

There exist a pattern $P$ of length $m=\Omega((D+k)^{1+o(1)}(k+1))$ and a text
$T$ of length $n\leq 3m/2$ such that the set of $k$-mismatch occurrences of
$P$ in $T$ cannot be covered with less than $\Omega((D+k)\cdot(k+1))$
arithmetic progressions.

######  Proof 5.2.

We call a set $S\subseteq[1\mathinner{.\,.}n]$ progression-free if it contains
no non-trivial arithmetic progression, that is, three distinct integers
$a,b,c$ such that $a+b-2c=0$.

######  Fact 9 ([21]).

For any sufficiently large $M$, there exists an integer
$n_{M}=\mathcal{O}(M2^{\sqrt{\log M}})$ and a progression-free set $S$ such
that $S$ has cardinality $M$ and $S\subseteq[n_{M}]$.

Let $M=D+k/2$ and $S\subseteq[n_{M}]$ be a progression-free set of cardinality
$M$. We encode $S$ in a string $P_{S}$ of size $n_{M}$ as follows: for every
$i\notin S$ we set $P_{S}[i]=0$, and we arbitrarily assign $k/2$ $1$s and $D$
wildcards to the remaining $D+k/2$ positions. We then consider the pattern
$P=0^{\ell}P_{S}0^{\ell}$, where $\ell$ is a parameter to be determined later.
In what follows, let $m:=2\ell+n_{M}$ denote the length of $P$.

Now, let $M^{\prime}=k/2+1$ and $S^{\prime}\subseteq[n_{M^{\prime}}]$ be a
progression-free set of cardinality $M^{\prime}$. We set
$T:=0^{m/2}B_{1}\ldots B_{n_{M^{\prime}}}0^{m/2}$, where $B_{i}=0^{t-1}1$ if
$i\in S^{\prime}$, $B_{i}=0^{t}$ otherwise, and $t=\lfloor
m/(2n_{M^{\prime}})\rfloor$. We pick $\ell$ large enough such that $t\geq
10n_{M}$ and $2n_{M^{\prime}}$ divides $m$. We have
$t=m/2n_{M^{\prime}}=(2\ell+n_{M})/2n_{M^{\prime}}\geq 10n_{M}$, which implies
that it suffices for $\ell$ to be larger than $n_{M}n_{M^{\prime}}$ by a
constant factor, i.e.,
$m=\Omega((k+D)(k+1)2^{\sqrt{\log(k+D)}+\sqrt{\log(k+1)}})$. Observe that
$i\in X$ if and only if there exists $j$ such that
$P[j]\in\\{1,\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>and $T[i+j]=1$. Moreover, any pair of $1$s in $T$ are at least $t\geq 10n_{M}$
positions apart, while the $1$s and wildcards of $P$ all lie within an
interval of size $n_{M}$. Therefore, for a given alignment of $P$ and $T$,
there can be at most one $1$ of $T$ that is aligned with a $1$ or a wildcard
of $P$; it follows that $X$ has cardinality
$(D+k/2)\cdot(k/2+1)=\Omega((D+k)\cdot(k+1))$.

It remains to show that $X$ does not contain arithmetic progressions of length
$3$. Assume for a sake of contradiction that there exist $x,y,z\in X$ with
$x<y<z$ that form an arithmetic progression, i.e., $y-x=z-y$. Let $i_{x}$
denote the index of the block $B_{i_{x}}$ of $T$ that contains the leftmost
$1$ that is aligned with a $1$ or a wildcard of $P$: this $1$ is at position
$m/2+i_{x}t$ in $T$. Similarly, let $d_{x}$ be such that the corresponding
aligned character is at position $\ell+d_{x}$ in $P$. Define
$i_{y},i_{z},d_{y},d_{z}$ similarly for $y,z$. We can express each
$w\in\\{x,y,z\\}$ in terms of $i_{w}$ and $d_{w}$ as
$w=m/2+i_{w}t-d_{w}-\ell+1$. Combining the above equations for $x$, $y$, and
$z$, we get $y-x=(i_{y}-i_{x})t-(d_{y}-d_{x})$ and
$z-y=(i_{z}-i_{y})t-(d_{z}-d_{y})$. By construction, $|d_{y}-d_{x}|\leq
n_{M}$. As $t\geq 10n_{M}$, the equality $y-x=z-y$ thus yields
$i_{y}-i_{x}=i_{z}-i_{y}$ and $d_{y}-d_{x}=d_{z}-d_{y}$. However, as $x<y<z$,
at least one of the above two equations involves non-zero values. In other
words, there is an three-term arithmetic progression in either $S$ or
$S^{\prime}$, contradicting the fact that they are progression-free.

## References

  * [1] Karl R. Abrahamson.  Generalized string matching.  SIAM Journal on Computing, 16(6):1039–1051, 1987.
  * [2] Andris Ambainis.  Quantum query algorithms and lower bounds.  In Classical and New Paradigms of Computation and their Complexity Hierarchies, pages 15–32, 2004.  doi:10.1007/978-1-4020-2776-5_2.
  * [3] Amihood Amir, Moshe Lewenstein, and Ely Porat.  Faster algorithms for string matching with k mismatches.  J. Algorithms, 50(2):257–275, 2004.  doi:10.1016/S0196-6774(03)00097-X.
  * [4] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter.  Elementary gates for quantum computation.  Physical Review A, 52:3457–3467, 1995.  doi:10.1103/PhysRevA.52.3457.
  * [5] Felix A. Behrend.  On sets of integers which contain no three terms in arithmetical progression.  Proceedings of the National Academy of Sciences, 32(12):331–332, 1946.
  * [6] Francine Blanchet-Sadri and Justin Lazarow.  Suffix trees for partial words and the longest common compatible prefix problem.  In LATA, volume 7810, pages 165–176. Springer, 2013.  doi:10.1007/978-3-642-37064-9\\_16.
  * [7] Karl Bringmann, Philip Wellnitz, and Marvin Künnemann.  Few matches or almost periodicity: Faster pattern matching with mismatches in compressed texts.  In SODA, pages 1126–1145, 2019.  doi:10.1137/1.9781611975482.69.
  * [8] Harry Buhrman and Ronald de Wolf.  Complexity measures and decision tree complexity: a survey.  Theoretical Computer Science, 288(1):21–43, 2002.  doi:10.1016/S0304-3975(01)00144-X.
  * [9] Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat.  Approximating text-to-pattern hamming distances.  In STOC, pages 643–656, 2020.  doi:10.1145/3357713.3384266.
  * [10] Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams, and Yinzhan Xu.  Faster algorithms for text-to-pattern hamming distances.  In FOCS, pages 2188–2203, 2023.  doi:10.1109/FOCS57990.2023.00136.
  * [11] Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, and Wiktor Zuba.  Circular pattern matching with _k_ mismatches.  J. Comput. Syst. Sci., 115:73–85, 2021.  doi:10.1016/j.jcss.2020.07.003.
  * [12] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz.  Faster approximate pattern matching: A unified approach.  In FOCS, pages 978–989, 2020.  doi:10.1109/FOCS46700.2020.00095.
  * [13] Peter Clifford and Raphaël Clifford.  Simple deterministic wildcard matching.  Inf. Process. Lett., 101(2):53–54, 2007.  doi:10.1016/j.ipl.2006.08.002.
  * [14] Raphaël Clifford, Klim Efremenko, Ely Porat, and Amir Rothschild.  From coding theory to efficient pattern matching.  In SODA, pages 778–784, 2009.
  * [15] Raphaël Clifford, Klim Efremenko, Ely Porat, and Amir Rothschild.  Pattern matching with don’t cares and few errors.  J. Comput. Syst. Sci., 76(2):115–124, 2010.  doi:10.1016/j.jcss.2009.06.002.
  * [16] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya.  The _k_ -mismatch problem revisited.  In SODA, pages 2039–2052, 2016.  doi:10.1137/1.9781611974331.CH142.
  * [17] Raphaël Clifford and Ely Porat.  A filtering algorithm for k-mismatch with don’t cares.  Inf. Process. Lett., 110(22):1021–1025, 2010.  doi:10.1016/j.ipl.2010.08.012.
  * [18] Richard Cole and Ramesh Hariharan.  Verifying candidate matches in sparse and wildcard matching.  In STOC, pages 592–601, 2002.  doi:10.1145/509907.509992.
  * [19] Maxime Crochemore, Christophe Hancart, and Thierry Lecroq.  Algorithms on Strings.  Cambridge University Press, 2007.  doi:10.1017/cbo9780511546853.
  * [20] Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Jakub Radoszewski, Wojciech Rytter, Bartosz Szreder, and Tomasz Walen.  A note on the longest common compatible prefix problem for partial words.  J. Discrete Algorithms, 34:49–53, 2015.  doi:10.1016/J.JDA.2015.05.003.
  * [21] Michael Elkin.  An improved construction of progression-free sets.  In SODA, pages 886–905, 2010.  doi:10.1137/1.9781611973075.72.
  * [22] Paul Erdös and Paul Turán.  On some sequences of integers.  Journal of the London Mathematical Society, s1-11(4):261–264, 1936\.  doi:10.1112/jlms/s1-11.4.261.
  * [23] Nathan J. Fine and Herbert S. Wilf.  Uniqueness theorems for periodic functions.  Proceedings of the American Mathematical Society, 16(1):109–114, 1965.  doi:10.2307/2034009.
  * [24] Paweł Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Łącki, and Piotr Sankowski.  Optimal dynamic strings.  In SODA, pages 1509–1528, 2018.  doi:10.1137/1.9781611975031.99.
  * [25] Pawel Gawrychowski and Przemyslaw Uznański.  Towards unified approximate pattern matching for Hamming and L_1 distance.  In ICALP, pages 62:1–62:13, 2018.  doi:10.4230/LIPIcs.ICALP.2018.62.
  * [26] Yijie Han.  Deterministic sorting in $O(n\log\log n)$ time and linear space.  J. Algorithms, 50(1):96–105, 2004.  doi:10.1016/j.jalgor.2003.09.001.
  * [27] Ramesh Hariharan and V. Vinay.  String matching in Õ(sqrt(n)+sqrt(m)) quantum time.  Journal of Discrete Algorithms, 1(1):103–110, 2003.  doi:10.1016/S1570-8667(03)00010-8.
  * [28] Piotr Indyk.  Faster algorithms for string matching problems: Matching the convolution bound.  In FOCS, pages 166–173, 1998.  doi:10.1109/SFCS.1998.743440.
  * [29] Ce Jin and Jakob Nogler.  Quantum speed-ups for string synchronizing sets, longest common substring, and _k_ -mismatch matching.  In SODA, pages 5090–5121, 2023.  doi:10.1137/1.9781611977554.ch186.
  * [30] Adam Kalai.  Efficient pattern-matching with don’t cares.  In SODA, pages 655–656, 2002.
  * [31] Dominik Kempa and Tomasz Kociumaka.  Dynamic suffix array with polylogarithmic queries and updates.  In STOC 2022, pages 1657–1670. ACM, 2022.  doi:10.1145/3519935.3520061.
  * [32] Donald E Knuth, James H Morris, Jr, and Vaughan R Pratt.  Fast pattern matching in strings.  SIAM journal on computing, 6(2):323–350, 1977.
  * [33] Tomasz Kociumaka, Ely Porat, and Tatiana Starikovskaya.  Small-space and streaming pattern matching with k edits.  In FOCS, pages 885–896, 2021.  doi:10.1109/FOCS52979.2021.00090.
  * [34] Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń.  Internal pattern matching queries in a text and applications.  In SODA, pages 532–551, 2015.  doi:10.1137/1.9781611973730.36.
  * [35] S. Rao Kosaraju.  Efficient string matching.  Unpublished manuscript, 1987.
  * [36] Gad M. Landau and Uzi Vishkin.  Efficient string matching with k mismatches.  volume 43, pages 239–249, 1986.  doi:10.1016/0304-3975(86)90178-7.
  * [37] Udi Manber and Ricardo A. Baeza-Yates.  An algorithm for string matching with a sequence of don’t cares.  Inf. Process. Lett., 37(3):133–136, 1991.  doi:10.1016/0020-0190(91)90032-D.
  * [38] Gerhard Mehldau and Gene Myers.  A system for pattern matching applications on biosequences.  Bioinformatics, 9(3):299–314, 1993.  doi:10.1093/bioinformatics/9.3.299.
  * [39] Michael S Paterson Michael J Fischer.  String-matching and other products.  In SCC, pages 113–125, 1974.
  * [40] Marius Nicolae and Sanguthevar Rajasekaran.  On string matching with mismatches.  Algorithms, 8(2):248–270, 2015.  doi:10.3390/a8020248.
  * [41] Marius Nicolae and Sanguthevar Rajasekaran.  On pattern matching with k mismatches and few don’t cares.  Inf. Process. Lett., 118:78–82, 2017.  doi:10.1016/j.ipl.2016.10.003.

##  Appendix A Verification of Occurrences via Kangaroo Jumping

Here, we provide a proof of 3, which we restate for convenience.

See 3

######  Proof A.1.

It suffices to use the kangaroo jumping technique [36]. We start at position
$1$ of the pattern with mismatch budget $k$. With one lcp query, we reach the
first position in the pattern where we have either a wildcard or a mismatch.
If it is a wildcard, we jump to the next non-wildcard character using another
lcp query (in more detail, we apply 2 with wildcards replaced by
$\$\notin\Sigma$); otherwise, we decrement the budget of mismatches by one and
continue from the next position. If the budget of mismatches becomes zero
before we reach the end of the $P$, then $P$ does not have a $k$-mismatch
occurrence at position $p$; otherwise it does. In each iteration we either
decrease the mismatch budget or jump over a group of wildcards. Hence, the
total number of performed lcp queries (which are the bottleneck) is
$\mathcal{O}(G+k)$.

##  Appendix B Omitted Proofs from Section 3

Here, we provide proofs of Lemma 3.3 and 4, which we restate for convenience.

See 3.3

######  Proof B.1.

It suffices to describe how to compute elements of the set
$\mathsf{RightMisper}(V,i,j,|V|)$ as the computation of elements of the set
$\mathsf{LeftMisper}(V,i,j,|V|)$ is symmetric.

We first compute the period $q$ of $V[i\mathinner{.\,.}j]$ in $\mathcal{O}(1)$
time in the PILLAR model. Let $Q:=V[i\mathinner{.\,.}i+q)$ and observe that
$Q^{2}$ is a prefix of $V[i\mathinner{.\,.}j]$ since the latter is periodic.
Hence, in constant time, we can retrieve a fragment of $V$ equal to any
desired rotation of $Q$.

Let us now discuss how to efficiently compute the first misperiod, that is,
the first mismatch between $V[i\mathinner{.\,.}|V|]$ and $Q^{\infty}$. Let $F$
be the maximal solid fragment that contains $V[i\mathinner{.\,.}j]$. Using 2,
in $\mathcal{O}(1)$ time in the PILLAR model, we either compute the first
misperiod or reach a group of wildcards and conclude that there are no
misperiods in $F$. In the latter case we do the following. While we have not
yet found a misperiod or reached the end of $V$, we consider the subsequent
maximal solid fragment $Y$; we find the starting position $y$ of this fragment
by applying 2 to compute the length of the encountered group of wildcards. The
elements of $\mathsf{RightMisper}(V,i,j,|V|)$ spanned by $Y$ are the
mismatches of $Y$ and $Q^{\infty}[y-i\mathinner{.\,.}y-i+|Y|)$. We can compute
the smallest such element, if one exists using 2, or reach the next group of
wildcards.

Subsequent misperiods are computed in an analogous manner using the kangaroo
method: we try to compute them in maximal solid fragments using 2 in
$\mathcal{O}(1)$ time in the PILLAR model, while skipping any encountered
groups of wildcards in $\mathcal{O}(1)$ time in the PILLAR model.

See 4

######  Proof B.2.

Towards a contradiction suppose that we have two $S$-runs $R_{1}$ and $R_{2}$
that overlap by at least $\textsf{per}(S)$ positions. Since $S$-runs
correspond to inclusion-maximal arithmetic progressions of occurrences of $S$,
the difference of the starting positions of $R_{1}$ and $R_{2}$ is not a
multiple of $\textsf{per}(S)$. Without loss of generality, suppose that the
starting position of $R_{1}$ is to the left of the starting position of
$R_{2}$. Then,
$S[1\mathinner{.\,.}\textsf{per}(S)]=R_{2}[1\mathinner{.\,.}\textsf{per}(S)]$
matches a non-trivial rotation of itself, and is hence not primitive, which
contradicts 1.

##  Appendix C Fast Algorithms in Various Settings

In this section, we combine the algorithm encapsulated in Theorem 1.2 with
efficient implementations of the PILLAR model in the standard, dynamic, fully
compressed, and quantum settings, thus obtaining efficient algorithms for
(approximate) pattern matching with wildcards in these settings. For ease of
presentation, we use the terms “exact occurrences” and “$0$-mismatch
occurrences” interchangeably.

#### Standard setting

In the standard setting, where a collection of strings of total length $N$ is
given explicitly, PILLAR operations can be performed in constant time after an
$\mathcal{O}(N)$-time preprocessing, cf. [12]. We thus obtain the following
result, by noticing that the $\log\log(D+k)$ factor in the complexity of
Theorem 1.2 only comes from sorting subsets of $[1\mathinner{.\,.}n]$ of total
size $\mathcal{O}((D+k)(G+k))$ in the calls to Lemma 4.3, which we can instead
do naively in $\mathcal{O}(n+(D+k)(G+k))$ time as we can batch the
computations.

######  Theorem C.1.

Let $P$ be a pattern of length $m$ with $D$ wildcards arranged in $G$ groups,
$T$ be a solid text of length $n$, and $k\geq 0$ be an integer. We can compute
a representation of the $k$-mismatch occurrences of $P$ in $T$ in
$\mathcal{O}(n+(D+k)\cdot(G+k))$ time.

#### Fully compressed setting

For our purposes, a straight-line program (SLP) is a context-free grammar
$\Gamma$ that consists of the set
$\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>of terminals and a set $N_{\Gamma}=\\{A_{1},\dots,A_{n}\\}$ of non-terminals
such that each $A_{i}\in N_{\Gamma}$ is associated with a unique production
rule $A_{i}\rightarrow
f_{\Gamma}(A_{i})\in(\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color@gray@fill{0.9}$\blacklozenge$}}}}\cup\\{A_{j}:j<i\\})^{*}$.
We can assume without loss of generality that each production rule is of the
form $A\rightarrow BC$ for some symbols $B$ and $C$ (that is, the given SLP is
in Chomsky normal form). Every symbol $A\in
S_{\Gamma}:=N_{\Gamma}\cup\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>generates a unique string, which we denote by
$\mathit{gen}(A)\in\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>The string $\mathit{gen}(A)$ can be obtained from $A$ by repeatedly replacing
each non-terminal with its production. We say that $\Gamma$ generates
$\mathit{gen}(\Gamma):=\mathit{gen}(A_{n})$.

In the fully compressed setting, given a collection of straight-line programs
(SLPs) of total size $n$ generating strings of total length $N$, each PILLAR
operation can be performed in $\mathcal{O}(\log^{2}N\log\log N)$ time after an
$\mathcal{O}(n\log N)$-time preprocessing, cf. [12]. Additionally, using a
dynamic programming approach, we can compute a linked-list representation of
all wildcards in $P$ in $\mathcal{O}(m+D)$ time. If we applied Theorem 1.2
directly in the fully compressed setting, we would obtain $\Omega(N/M)$ time,
where $N$ and $M$ are the uncompressed lengths of the text and the pattern,
respectively. Instead, we can adapt a dynamic programming approach described
in [12, Section 7.2] to obtain the following result.

######  Theorem C.2 (Fully Compressed Setting).

Let $\Gamma_{T}$ denote a straight-line program of size $n$ generating a solid
string $T$, let $\Gamma_{P}$ denote a straight-line program of size $m$
generating a string $P$ with $D$ wildcards arranged in $G$ groups, let $k\geq
0$ denote an integer threshold, and set $N:=|T|$ and $M:=|P|$. We can compute
the number of $k$-mismatch occurrences of $P$ in $T$ in $\mathcal{O}(m\log
N+n(D+k)(G+k)\log^{2}N\log\log N)$ time. All occurrences can be returned in
extra time proportional to the output size.

#### Dynamic setting

Let $\mathcal{X}$ be a growing collection of non-empty persistent strings; it
is initially empty, and then undergoes updates by means of the following
operations:

  * •

$\texttt{Makestring}(U)$: Insert a non-empty string $U$ to $\mathcal{X}$

  * •

$\texttt{Concat}(U,V)$: Insert string $UV$ to $\mathcal{X}$, for
$U,V\in\mathcal{X}$

  * •

$\texttt{Split}(U,i)$: Insert $U[0\mathinner{.\,.}i)$ and
$U[i\mathinner{.\,.}|U|)$ to $\mathcal{X}$, for $U\in\mathcal{X}$ and
$i\in[0\mathinner{.\,.}|U|)$.

By $N$ we denote an upper bound on the total length of all strings in
$\mathcal{X}$ throughout all updates executed by an algorithm. A collection
$\mathcal{X}$ of non-empty persistent strings of total length $N$ can be
dynamically maintained with operations $\mathtt{Makestring}(U)$,
$\mathtt{Concat}(U,V)$, $\mathtt{Split}(U,i)$ requiring time
$\mathcal{O}(|U|\cdot\log N)$, $\mathcal{O}(\log^{2}N)$ and
$\mathcal{O}(\log^{2}N)$, respectively, so that PILLAR operations can be
performed in time $\mathcal{O}(\log^{2}N)$. Furthermore, one can find all
occurrences of a pattern of length $\ell$ in a string in $\mathcal{X}$ in
$\mathcal{O}(\ell+\log^{2}N+\mathrm{occ}\cdot\log N)$ time, where
$\mathrm{occ}$ is the size of the output. All stated time complexities hold
with probability $1-1/N^{\Omega(1)}$; see [24, 12]. To compute the linked list
representation of the endpoints of groups of wildcards for a string
$X\in\mathcal{X}$, we simply use pattern matching for a pattern $P=\\#$. The
complexity of this step is dominated by the time required by our (approximate)
pattern matching algorithm.

######  Theorem C.3 (Dynamic Setting).

A collection $\mathcal{X}$ of non-empty persistent strings of total length $N$
over alphabet
$\Sigma_{\scalebox{0.7}{\stackinset{c}{}{c}{}{$\lozenge$}{{\color[rgb]{0.9,0.9,0.9}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0.9,0.9}\pgfsys@color@gray@stroke{0.9}\pgfsys@color<EMAIL_ADDRESS>can be dynamically maintained with operations $\mathtt{Makestring}(U)$,
$\mathtt{Concat}(U,V)$, $\mathtt{Split}(U,i)$ requiring time
$\mathcal{O}(|U|\cdot\log N)$, $\mathcal{O}(\log^{2}N)$, and
$\mathcal{O}(\log^{2}N)$, respectively, so that, given two strings
$P,T\in\mathcal{X}$, such that $P$ has $D$ wildcards arranged in $G$ groups
and $T$ is a solid string, and an integer threshold $k\geq 0$, we can return a
representation of all $k$-mismatch occurrences of $P$ in $T$ in time
$\mathcal{O}((D+k)(G+k)\cdot|T|/|P|\cdot\log^{2}N)$ time. All stated time
complexities hold with probability $1-1/N^{\Omega(1)}$.

Kempa and Kociumaka [31, Section 8 in the arXiv version] presented a
deterministic implementation of a collection $\mathcal{X}$ of non-empty
persistent strings, which allows to remove randomness from the statement of
Theorem C.3 at the expense of replacing the $\log N$ factors with
$\operatorname{polylog}N$.

#### Quantum setting

We say an algorithm on an input of size $n$ succeeds _with high probability_
if the success probability can be made at least $1-1/n^{c}$ for any desired
constant $c>1$.

In what follows, we assume the input strings can be accessed in a quantum
query model [2, 8]. We are interested in the time complexity of our quantum
algorithms [4].

[[29, Observation 2.3]] For any two strings $S,T$ of length at most $n$,
$\textsf{lcp}(S,T)$ or $\textsf{lcp}^{R}(S,T)$ can be computed in
$\tilde{\mathcal{O}}(\sqrt{n})$ time in the quantum model with high
probability.

Hariharan and Vinay [27] gave a near-optimal quantum algorithm for the
decision version of exact pattern matching. We formalize this next.

######  Theorem C.4 ([27]).

For any two strings $S,T$ of length at most $n$, there is a quantum algorithm
that can determine, with high probability, whether $S$ occurs in $T$ correctly
in $\widetilde{\mathcal{O}}(\sqrt{n})$ time. If the answer is affirmative, the
algorithm provides an occurrence of $S$ in $T$.

######  Corollary C.5.

For any two strings $S,T$ of length at most $n$, with $|T|\leq 2|S|$,
$\mathsf{IPM}(S,T)$ can be computed in $\tilde{\mathcal{O}}(\sqrt{n})$ time in
the quantum model with high probability.

######  Proof C.6.

We apply Theorem C.4 and binary search to find the period of $S$ [34] and thus
its full list of occurrences expressed as an arithmetic progression in $T$.

All other PILLAR operations are performed trivially in $\mathcal{O}(1)$
quantum time. Thus while all PILLAR operations can be implemented in
$\mathcal{O}(1)$ time after $\mathcal{O}(n)$-time preprocessing in the
standard setting by a classic algorithm, in the quantum setting, all PILLAR
operations can be implemented in $\tilde{\mathcal{O}}(\sqrt{m})$ quantum time
_with no preprocessing_ , as we always deal with strings of length
$\mathcal{O}(m)$. Additionally, we can compute the linked list representation
of the endpoints of groups of wildcards in $\tilde{\mathcal{O}}(\sqrt{m}G)$
time in the quantum model with high probability as follows: we search for a
wildcard and, if we find it, we compute the group that contains it in
$\mathcal{O}(1)$ time in the PILLAR model using 2; we then recurse on both
sides of the group, and so on. In total, this procedure requires
$\mathcal{O}(G)$ time in the PILLAR model and hence
$\tilde{\mathcal{O}}(\sqrt{m}G)$ time in the quantum model. As we always deal
with strings of length $\mathcal{O}(m)$, we obtain the following result.

######  Theorem C.7 (Quantum Setting).

Consider a length-$m$ string $P$ with $D$ wildcards arranged in $G$ groups, a
solid length-$n$ string $T$, and an integer threshold $k\geq 0$. The
$k$-mismatch occurrences of $P$ in $T$ can be computed in
$\tilde{\mathcal{O}}((n/\sqrt{m})(G+k)(D+k))$ time in the quantum model with
high probability.