Giulia Bernardini

Esteban Gabory

Solon P Pissis

Leen Stougie

Michelle Sweering

Wiktor Zuba

Elastic-Degenerate String Matching with 1 Error

Introduction

String matching (or pattern matching) is a fundamental task in computer science, for which several lineartime algorithms are known [START_REF] Crochemore | Algorithms on strings[END_REF]. It consists in finding all occurrences of a short string, known as the pattern, in a longer string, known as the text. Many representations have been introduced over the years to account for unknown or uncertain letters in the pattern or in the text, a phenomenon that often occurs in real data. In the context of computational biology, for example, the IUPAC notation [START_REF]IUPAC-IUB Commission on Biochemical Nomenclature. Abbreviations and symbols for nucleic acids, polynucleotides, and their constituents[END_REF] is used to represent locations of a DNA sequence for which several alternative nucleotides are possible. Such a notation can encode the consensus of a population of DNA sequences [START_REF]Computational pan-genomics: status, promises and challenges[END_REF][START_REF] Alzamel | Degenerate string comparison and applications[END_REF][START_REF] Alzamel | Comparing degenerate strings[END_REF][START_REF] Gawrychowski | On indeterminate strings matching[END_REF] in a gapless multiple sequence alignment (MSA). Figure 1: An MSA of three sequences and its (non-unique) representation T as an ED string of length n = 7 and size N = 20. The only two exact occurrences of P = TTA in T end at positions 6 (black underline) and 7 (blue overline); a 1-mismatch occurrence of P in T ends at position 2 (green underline); and a 1-error occurrence of P in T ends at position 3 (red overline). Note that other 1-error and 1-mismatch occurrences of P in T exist (e.g., ending at positions 1 and 5).

EDSM Features Running time

Grossi et al. [START_REF] Grossi | On-line pattern matching on similar texts[END_REF] Combinatorial O(nm 2 + N ) Aoyama et al. [START_REF] Aoyama | Faster online elastic degenerate string matching[END_REF] Fast Fourier transform O(nm 1.5 √ log m + N ) Bernardini et al. [START_REF] Bernardini | Even faster elastic-degenerate string matching via fast matrix multiplication[END_REF] Fast matrix multiplication O(nm 1.381 + N ) Bernardini et al. [START_REF] Bernardini | Elasticdegenerate string matching via fast matrix multiplication[END_REF] Fast matrix multiplication Õ(nm ω-1 ) + O(N ) Table 1: The upper-bound landscape of the EDSM problem. The term "combinatorial" is arguably not well-defined; lower bounds conditioned on Boolean Matrix Multiplication often indicate that other techniques, including fast matrix multiplication, may be employed to obtain improved bounds for a specific problem. This is the case for EDSM. [START_REF] Costas | Efficient pattern matching in elastic-degenerate strings[END_REF] to also encode insertions and deletions (gaps) occurring in MSAs by introducing the notion of elastic-degenerate strings. An elastic-degenerate (ED) string T over an alphabet Σ is a sequence of finite subsets of Σ * (which includes the empty string ε), called segments. The total number of segments is the length of the ED string, denoted by n = | T |; and the total number of letters (including symbol ε) in all segments is the size of the ED string, denoted by N = T . Inspect Figure 1 for an example.

Iliopoulos et al. generalized these representations in

A natural problem is to find all occurrences of a standard (non-degenerate) pattern P in an ED text T , called the ED string matching (EDSM) problem in the literature. After the simple polynomial-time algorithm proposed by Iliopoulos et al. [START_REF] Costas | Efficient pattern matching in elastic-degenerate strings[END_REF], a series of results have been published for EDSM. The results for EDSM summarized in Table 1 have a linear dependency on the size N of the ED text, a highly desirable property. (A different line of research exists, which waives the linear-dependency restriction, and employs bit-vector techniques to speed up the computation specifically for short patterns [START_REF] Grossi | On-line pattern matching on similar texts[END_REF][START_REF] Solon | Dictionary matching in elastic-degenerate texts with applications in searching VCF files on-line[END_REF][START_REF] Cislak | SOPanG: online text searching over a pangenome[END_REF].) In Table 1, m is the length of the pattern, n is the length of the ED text, N is its size, and ω is the matrix multiplication exponent. These algorithms are also on-line: the ED text is read segment-by-segment and occurrences are reported as soon as the last segment they overlap is processed. Grossi et al. [START_REF] Grossi | On-line pattern matching on similar texts[END_REF] presented an O(nm 2 +N )-time algorithm for EDSM. This was later improved by Aoyama et al. [START_REF] Aoyama | Faster online elastic degenerate string matching[END_REF], who employed fast Fourier transform to improve the time complexity of EDSM to O(nm 1.5 √ log m + N ). Bernardini et al. [START_REF] Bernardini | Even faster elastic-degenerate string matching via fast matrix multiplication[END_REF] then presented a lower bound conditioned on Boolean Matrix Multiplication suggesting that it is unlikely to solve EDSM by a combinatorial algorithm in O(nm 1.5-+ N ) time, for any > 0. This was an indication that fast matrix multiplication may improve the time complexity of EDSM. Indeed, Bernardini et al. [START_REF] Bernardini | Even faster elastic-degenerate string matching via fast matrix multiplication[END_REF] presented an O(nm 1.381 + N )-time algorithm, which they subsequently improved to an Õ(nm ω-1 ) + O(N )-time algorithm [START_REF] Bernardini | Elasticdegenerate string matching via fast matrix multiplication[END_REF], both using fast matrix multiplication, thus breaking through the conditional lower bound for EDSM.

Our Results and Techniques

In string matching, a single extra or missing letter in the pattern or in a potential occurrence results in missing (many or all) occurrences. Hence, many works are focused on approximate string matching for standard strings [START_REF] Gad | Efficient string matching with k mismatches[END_REF][START_REF] Gad | Fast string matching with k differences[END_REF][START_REF] Cole | Approximate string matching: A simpler faster algorithm[END_REF][START_REF] Amir | Faster algorithms for string matching with k mismatches[END_REF][START_REF] Gawrychowski | Towards unified approximate pattern matching for Hamming and l 1 distance[END_REF][START_REF] Charalampopoulos | Faster approximate pattern matching: A unified approach[END_REF]. For approximate k-EDSM, Bernardini et al. [START_REF] Bernardini | Approximate pattern matching on elastic-degenerate text[END_REF] presented an on-line O(k 2 mG + kN )-time algorithm under edit distance and an on-line O(kmG + kN )-time algorithm under Hamming distance, where k is the maximum allowed number of errors (edits) or mismatches, respectively, and G is the total number of strings in all segments. Unfortunately, G is only bounded by N , and so even for k = 1, the existing algorithms run in Ω(mN ) time in the worst case.

Approximate EDSM Features

Running time

Bernardini et al. [START_REF] Bernardini | Approximate pattern matching on elastic-degenerate text[END_REF] k errors O(k Let us remark that the special case of k = 1 is not interesting for approximate string matching on standard strings: the existing algorithms have a polynomial dependency on k and a linear dependency on the length n of the text, and thus for k = 1 we trivially obtain O(n)-time algorithms under edit or Hamming distance. However, this is not the case for other string problems, such as text indexing with errors, where the first step was to design a data structure for 1 error [START_REF] Amir | Text indexing and dictionary matching with one error[END_REF]. The next step, extending it to k errors, required the development of new highly non-trivial techniques and incurred some exponential factor with respect to k [START_REF] Cole | Dictionary matching and indexing with errors and don't cares[END_REF]. Interestingly, k-EDSM seems to be the same case, which highlights the main theoretical motivation of this paper. In Table 2, we summarize the state of the art for approximate EDSM and our new results for k = 1. Note that the reporting algorithms underlying our results are also on-line.

Indeed, to arrive at our main results, we design a rich non-trivial combination of algorithmic techniques. Our algorithms for edit distance rely on non-trivial reductions from 1-EDSM to special instances of classic computational geometry problems (2d rectangle stabbing or 2d range emptiness), which we show how to solve efficiently. In order to obtain an even faster algorithm for Hamming distance, we also rely on employing and adapting the k-errata trees of Cole et al. for text indexing with k errors [START_REF] Cole | Dictionary matching and indexing with errors and don't cares[END_REF].

The combinatorial algorithms we develop here for approximate EDSM are good in the following sense. First, the running times of our algorithms do not depend on G, a highly desirable property. Specifically, all of our results replace m • G by an n • poly(m) factor. Second, our Õ(nm 2 + N )-time algorithms are at most one log m factor slower than O(nm 2 + N ), the best-known bound obtained by a combinatorial algorithm (not employing fast Fourier transforms) for exact EDSM [START_REF] Grossi | On-line pattern matching on similar texts[END_REF]. Notably, for Hamming distance, we show an O(nm 2 + N log m)-time algorithm. Last, our O(nm 3 + N )-time algorithms have a linear dependency on N , another highly desirable property (at the expense of an extra m-factor).

Other Related Work The main motivation to consider ED strings is that they can be used to represent a pangenome: a collection of closely-related genomic sequences that are meant to be analyzed together [START_REF]Computational pan-genomics: status, promises and challenges[END_REF]. Several other pangenome representations have been proposed in the literature, mostly graph-based ones; see [START_REF] Carletti | Graph-based representations for supporting genome data analysis and visualization: Opportunities and challenges[END_REF] for a comprehensive overview by Carletti et al. Compared to these graph-based representations, ED strings have at least two main advantages in the context of string matching, as they support: (i) simple on-line string matching; and (ii) (deterministic) subquadratic in m string matching [START_REF] Aoyama | Faster online elastic degenerate string matching[END_REF][START_REF] Bernardini | Even faster elastic-degenerate string matching via fast matrix multiplication[END_REF][START_REF] Bernardini | Elasticdegenerate string matching via fast matrix multiplication[END_REF].

Similar in spirit to ED strings, and to the restricted notion of generalized degenerate strings, in which strings of different lengths cannot be in the same segment [START_REF] Alzamel | Degenerate string comparison and applications[END_REF][START_REF] Alzamel | Comparing degenerate strings[END_REF], is the representation of pangenomes via founder graphs. The idea behind founder graphs is that a multiple alignment of few founder sequences can be used to approximate the input MSA, with the feature that each row of the MSA is a recombination of the founders. Unlike ED strings, that are believed not to be efficiently indexable [START_REF] Gibney | An efficient elastic-degenerate text index? not likely[END_REF] (and indeed their value is to enable fast on-line string matching algorithms), some subclasses of founder graphs are, and a recent line of research is devoted to constructing and indexing such structures [START_REF] Veli Mäkinen | Linear time construction of indexable founder block graphs[END_REF][START_REF] Equi | Algorithms and complexity on indexing elastic founder graphs[END_REF]. Like founder graphs, ED strings support the recombination of different rows of the MSA between consecutive columns.

Paper Organization In Section 2, we provide the necessary definitions and notation, we describe the basic layout of the developed algorithms, and we formally state our main results. In Section 3, we present our solutions under edit distance; and in Section 4, we present our improvement for the special case of Hamming distance. In Section 5, we conclude this work with some basic open questions for future work.

Preliminaries

We start with some basic definitions and notation following [START_REF] Crochemore | Algorithms on strings[END_REF]. Let X = X [START_REF] Alzamel | Degenerate string comparison and applications[END_REF] . . . X[n] be a string of length |X| = n over an ordered alphabet Σ whose elements are called letters. The empty string is the string of length 0; we denote it by ε. For any two positions i and j ≥ i of X, X[i . . j] is the fragment of X starting at position i and ending at position j. The fragment X[i . . j] is an occurrence of the underlying substring P = X[i] . . . X[j]; we say that P occurs at position i in X. A prefix of X is a fragment of the form X[1 . . j] and a suffix of X is a fragment of the form X[i . . n]. By XY or X • Y we denote the concatenation of two strings X and Y , i.e., XY = X

[1] . . . X[|X|]Y [1] . . . Y [|Y |]. Given a string X we write X R = X[|X|] . . . X[1]
for the reverse of X. Given two strings X and Y we write LCP(X, Y ) for the length of their longest common prefix, namely for the integer max({i, X[1 .

. i] = Y [1 . . i]}), or 0 if X[1] = Y [1].
An elastic-degenerate string (ED string) T = T [START_REF] Alzamel | Degenerate string comparison and applications[END_REF] . . . T [n] over an alphabet Σ is a sequence of n = | T | finite sets, called segments, such that for every position i of T we have that T [i] ⊂ Σ * . By N = || T || we denote the total length of all strings in all segments of T , which we call the size of T ; more formally,

N = n i=1 | T [i]| j=1 | T [i][j]|,
[i][j] = ε, then we have that | T [i][j]| = 1.) Given two sets of strings S 1 and S 2 , their concatenation is S 1 • S 2 = {XY | X ∈ S 1 , Y ∈ S 2 }. For an ED string T = T [1] . . . T [n], we define the language of T as L( T ) = T [1] • . . . • T [n]. Given a set S of strings we write S R for the set {X R | X ∈ S}. For an ED string T = T [1] . . . T [n] we write T R for the ED string T [n] R . . . T [1] R .
Given a string P and an ED string T , we say that P matches the fragment T [j . . j ] = T [j] . . . T [j ] of T , or that an occurrence of P starts at position j and ends at position j in T if there exist two strings U, V , each of them possibly empty, such that P = P j • . . . • P j , where P i ∈ T [i], for every j < i < j , U • P j ∈ T [j], and

P j • V ∈ T [j ] (or U • P j • V ∈ T [
j] when j = j ). Strings U, V and P i , for every j ≤ i ≤ j , specify an alignment of P with T [j . . j ]. For each occurrence of P in T , the alignment is, in general, not unique. In Figure 1, P = TTA matches T [5 . . 6] with two alignments: both have U = ε, P 5 = TT, P 6 = A, and V is either C or CAC.

We want to accept matches with edit distance at most 1 according to the following standard definition:

Definition 1. Given two strings P and Q over an alphabet Σ, we define the edit distance d E (P, Q) between P and Q as the length of a shortest sequence of string operations π 1 , . . . , π such that Q = (Π i=1 π i )(P ), where each π i (for 1 ≤ i ≤ ) is one of the following type:

• Replacement: There is j ∈ [1, |P |] and σ = P [j] ∈ Σ s.t. π i (P )[j] = σ and π i (P )[j ] = P [j ] for j = j. • Deletion: One has |π i (P )| = |P | -1 and there is j ∈ [1, |P |] s.t. π i (P )[j ] = P [j ] for 1 ≤ j ≤ j -1 and π i (P )[j ] = P [j + 1] for j ≤ j ≤ |P | -1. • Insertion: One has |π i (P )| = |P | + 1 and there is j ∈ [1, |P | + 1] s.t. π i (P )[j ] = P [j ] for 1 ≤ j ≤ j -1 and π i (P )[j ] = P [j -1] for j + 1 ≤ j ≤ |P | + 1. Lemma 1 ([19]). The function d E is a distance on Σ * .
The following lemma follows immediately from Definition 1.

Lemma 2. If P , Q are two strings with d E (P, Q) = 1, then P = π(Q) where π is a replacement, a deletion or an insertion.

We define the main problem considered in this paper as follows:

1-Error EDSM Input: A string P of length m and an ED string T of length n and size N .

Output: All positions j in T such that there is at least one string P with an occurrence ending at position j in T , and with d E (P, P ) ≤ 1 (reporting version); or YES if and only if there is at least one string P with an occurrence in T , and with d E (P, P ) ≤ 1 (decision version).

Let P be a string starting at position j and ending at position j in T with d E (P, P ) = 1. We call this an occurrence of P with 1 error (or a 1-error occurrence); or equivalently, we say that P matches T [j . . j ] with 1 error. Let U P j , . . . , P j V be an alignment of P with T [j . . j ] and i ∈ [j, j ] be an integer such that the single replacement, insertion, or deletion required to obtain P from P = P j • . . . • P j occurs on P i . We then say that the alignment (and the occurrence) has the 1 error in T Hamming distance, denoted by d H , is a special case of edit distance in which only replacement operations are allowed (it is therefore defined for two strings of equal length). We define the following problem:

1-Mismatch EDSM Input: A string P of length m and an ED string T of length n and size N . Output: All positions j in T such that there is at least one string P with an occurrence ending at position j in T , and with d H (P, P ) ≤ 1.

An occurrence of a string P as in the problem definition is called an occurrence of P with 1 mismatch. We call mismatch the single position in the support of the replacement π such that π(P ) = P . We show the following theorem.

• AP i ⊆ [1, m], such that j ∈ AP i if and only if P [1 . . j] is an active prefix of P in T ending in the segment T [i],
that is, a prefix of P which is also a suffix of a string in L( T [START_REF] Alzamel | Degenerate string comparison and applications[END_REF] . . . T [i]).

• AS i ⊆ [1, m], such that j ∈ AS i if and only if P [j .
. m] is an active suffix of P in T starting in the segment T [i], that is, a suffix of P which is also a prefix of a string in L(

T [i] . . . T [n]). • 1-AP i ⊆ [1, m], such that j ∈ 1-AP i if and only if P [1 .
. j] is an active prefix with 1 error of P in T ending in the segment T [i], that is, a prefix of P which is also at distance at most 1 from a suffix of a string in

L( T [1] . . . T [i]).
For convenience we also define

AP 0 = AS n+1 = 1-AP 0 = ∅.
The following lemma shows that the computation of active suffixes can be easily reduced to computing the active prefixes for the reversed strings. Proof.

P R [1 . . m -j + 1] = (P [j . . m]) R of P R is an active prefix in T R , ending in the segment T R [n -i + 1] = ( T [i]) R . Prefix Case (Section 3.3) Anchor Case (Section 3.2) Suffix Case (Section 3.3) Easy Case (Section 3.1) AP i-1 AP i 1-AP i-1 1-AP i * * * *
If P [j . . m] is a prefix of S ∈ L( T [i . . n]), then P R [1 . . m-j+1] is a suffix of S R ∈ L( T [1 . . . n] R ). From the definition of T R we have T [i . . n] R = ( T [n]) R . . . ( T [i]) R = T R [1 . . n -i + 1], hence S R ∈ L( T R [1 . . n - i + 1]).
This proves the forward direction of the lemma; the converse follows from symmetry.

The efficient computation of active prefixes was shown in [START_REF] Grossi | On-line pattern matching on similar texts[END_REF], and constitutes the main part of the combinatorial algorithm for exact EDSM. Similarly, computing the sets 1-AP plays the key role in the reporting version of our algorithm for 1-Error EDSM (see Figure 2). Finding active prefixes (and, by Lemma 3, suffixes) reduces to the following problem, formalized in [START_REF] Bernardini | Even faster elastic-degenerate string matching via fast matrix multiplication[END_REF].

Active Prefixes Extension (APE)

Input: A string P of length m, a bit vector U of size m, and a set S of strings of total length N . Output: A bit vector V of size m with V [j] = 1 if and only if there exists S ∈ S and i ∈ As depicted in Figure 2, the computation of active prefixes with 1 error (1-AP i ) and the reporting of occurrences with 1 error reduce to a problem where the error can only occur in a single, fixed T [i]. In particular, this problem decomposes into 4 cases, which we formalize in the following proposition. Proposition 4. Let T = T [START_REF] Alzamel | Degenerate string comparison and applications[END_REF] . . . T [n] be an ED text and P be a pattern that has an occurrence with 1 error (resp. 1 mismatch) in T . For each alignment corresponding to such occurrence, at least one of the following is true:

[1, m], such that P [1 . . i] • S = P [1 . . j] and U [i] = 1.
Easy Case: P matches T [i] with 1 error (resp. 1 mismatch) for some 1 ≤ i ≤ n.

Anchor Case: P matches T [j . . j ] with 1 error (resp. 1 mismatch) in T [i] for some 1 ≤ j < i < j ≤ n.

T [i] is called the anchor of the alignment.

Prefix Case: P matches T [j . . i] with 1 error (resp. 1 mismatch) in T [i] for some 1 ≤ j < i ≤ n, implying an active prefix of P which is a suffix of a string in L( T [j . . i -1]).

Suffix Case: P matches T [i . . j ] with 1 error (resp. 1 mismatch) in T [i] for some 1 ≤ i < j ≤ n, implying an active suffix of P which is a prefix of a string in L( T [i + 1 . . j ]).

Proof. Suppose P has a 1-error (resp. 1 mismatch) occurrence matching T [j . . j ] with 1 ≤ j ≤ j ≤ n. If j = j we are in the Easy Case. Otherwise, each alignment has an error in some T [i] for j ≤ i ≤ j . If j < i < j , we are in the Anchor Case; if j < i = j , we are in the Prefix Case; and if j = i < j , we are in the Suffix Case.

1-Error EDSM

In this section, we present algorithms for finding all 1-occurrences of P given by each type of possible alignment described by Proposition 4 (inspect Figure 3). The Prefix and Suffix cases are analogous by Lemma 3; the only difference is in that, while the Suffix Case computes new 1-AP , the Prefix Case is used to actually report occurrences. They are jointly considered in Section 3.3. We follow two different procedures for the decision and reporting versions. For the decision version, we precompute sets AP i and AS i , for all i ∈ [1, n], using Corollary 3, and we simultaneously compute possible exact occurrences of P . Then we compute 1-error occurrences of P by grouping the alignments depending on the segment i in which the error occurs, and using AP i and AS i . For the reporting version, we consider one segment T [i] at a time (on-line) and extend partial exact or 1-error occurrences of P to compute sets AP i and 1-AP i using just sets AP i-1 and 1-AP i-1 computed at the previous step. We design different procedures for the 4 cases of Proposition 4. We can sort all letters of P , assign them rank values from [1, m], and construct a perfect hash table over these letters supporting O(1)-time look-up queries in O(m log m) time [START_REF] Ruzic | Constructing efficient dictionaries in close to sorting time[END_REF]. Any letter of T not occurring in P can be replaced by the same special letter in O(1) time. In the rest we thus assume that the input strings are over [1, m + 1].

Two problems from computational geometry have a key role in our solutions. We assume the word RAM model with coordinates on the integer grid [1, n] d = {1, 2, . . . , n} d . In the 2d rectangle emptiness problem, we are given a set P of n points to be preprocessed, so that when one gives an axis-aligned rectangle as a query, we report YES if and only if the rectangle contains a point from P. In the "dual" 2d rectangle stabbing problem, we are given a set R of n axis-aligned rectangles to be preprocessed, so that when one gives a point as a query, we report YES if and only if there exists a rectangle from R containing the point.

Lemma 5 ([11, 23]). After O(n √ log n)-time preprocessing, we can answer 2d rectangle emptiness queries in O(log log n) time. Lemma 6 ([15,[START_REF] Shi | Novel transformation techniques using q-heaps with applications to computational geometry[END_REF]). After O(n log n)-time preprocessing, we can answer 2d rectangle stabbing queries in O(log n) time.

In Section 3.4, we note that the 2d rectangle stabbing instances arising from 1-Error EDSM have a special structure. We show how to solve them efficiently thus shaving logarithmic factors from the time complexity.

Easy Case

The Easy Case can be reduced to approximate string matching with at most 1 error (1-SM):

1-SM Input: A string P of length m and a string T of length n. Output: All positions j in T such that there is at least one string P ending at position j in T with d E (P, P ) ≤ 1.

We have the following well-known results.

Lemma 7 ( [START_REF] Gad | Fast string matching with k differences[END_REF][START_REF] Cole | Approximate string matching: A simpler faster algorithm[END_REF]). Given a pattern P of length m, a text T of length n, and an integer k > 0, all positions j in T such that the edit distance of T [i . . j] and P , for some position i ≤ j on T , is at most k, can be found in O(kn) time or in O( nk 4 m + n) time. 1 In particular, 1-SM can be solved in O(n) time.

We find occurrences of P with at most 1 error that are in the Easy Case for segment T [i] in the following way: we apply Lemma 7 for k = 1 and every string of T [i] whose length is at least m -1 (any shorter string is clearly not relevant for this case) as text. If, for any of those strings, we find an occurrence of P , we report an occurrence at position i (inspect Figure 3a). The time for processing a segment T [i] is O(N i ), where N i is the total length of all the strings in T [i].

Anchor Case

Let T be an ED text and P be a pattern with a 1-error occurrence and an alignment in the Anchor Case with anchor T [i]. Further let L = P [1 . . ]S and Q = S P [q . . m] be a prefix and a suffix of P , respectively, for some ∈ AP i-1 , q ∈ AS i+1 , where S , S are a prefix and a suffix of some S ∈ T [i], respectively (strings S , S can be empty). By Lemma 2, a pair L, Q gives a 1-error occurrence of P if one of the following holds: 3b). We show how to find such pairs with the use of a geometric approach. For convenience, we only present the Hamming distance (1 mismatch) case. The other cases are handled similarly.

1 mismatch: |L| + |Q| + 1 = m and |S | + |S | + 1 = |S| (inspect Figure
Let λ ∈ AP i-1 be the length of an active prefix, and let ρ be the length of an active suffix, that is, m -ρ + 1 ∈ AS i+1 . Note that AP i-1 and AS i+1 can be precomputed, for all i, in O(nm 2 + N ) total time by means of Corollary 3. (In particular, AS i+1 is required only for the decision version; for the reporting version, we explain later on how to avoid the precomputation of AS i+1 to obtain an on-line algorithm.) We will exhaustively consider all pairs (λ, ρ) such that λ + ρ < m. Clearly, there are O(m 2 ) such pairs.

Consider the length µ = m -(λ + ρ) > 0 of the substring of P still to be matched for some prefix and suffix of P of lengths (λ, ρ), respectively. We group together all pairs (λ, ρ) such that m -(λ + ρ) = µ by sorting them in O(m 2 ) time. We construct, for each such group µ, the compacted trie T µ of the fragments P [λ + 1 . . m -ρ], for all (λ, ρ) such that m -(λ + ρ) = µ, and analogously the compacted trie T R µ of all fragments P R [ρ + 1 . . m -λ]. For each group µ, this takes O(m) time [START_REF] Joong | Truncated suffix trees and their application to data compression[END_REF]. We enhance all nodes with a perfect hash table in O(m) total time to access edges by the first letter of their label in O(1) time [START_REF] Michael | Storing a sparse table with 0(1) worst case access time[END_REF].

We also group all strings in segment T [i] of length less than m by their length µ. The group for length µ is denoted by G µ . This takes O(N i ) time. Clearly, the strings in G µ are the only candidates to extend pairs (λ, ρ) such that m -(λ + ρ) = µ. Note that the mismatch can be at any position of any string of G µ : its position determines a prefix S of length h and a suffix S of length k of the same string S, with h + k = µ -1, that must match a prefix and a suffix of P [λ + 1 . . m -ρ], respectively. We will consider 1 . 11] = bab; the 5 rectangles correspond to pairs (ε, aa), (a, a), (aa, ε), (ε, ab), (b, a), namely, the pairs of prefixes and reversed suffixes of aaa and bba (rectangle (bb, ε) does not exist as T3 contains no node bb).

P R [ρ + 1 . . m -λ] for the same pair (λ, ρ). This denotes that the two leaves correspond to the same fragment of P . For every (T µ , T R µ ), this preprocessing takes O(m √ log m) time by Lemma 5, since is O(µ) = O(m). For all µ groups (they are at most m), the whole preprocessing thus takes O(m 2 √ log m) time. We then ask 2d range emptiness queries that take O(log log m) time each by Lemma 5. Note that all rectangles for S can be collected in O(|S|) = O(µ) time by spelling S through T µ and S R through T R µ , one letter at a time. Thus the total time for processing all G µ groups of segment i is O(m 2 √ log m+N i log log m). If any of the queried ranges turns out to be non-empty, then P such that d H (P, P ) ≤ 1 appears in L( T ) with anchor in T [i]; we do not have sufficient information to output its ending position however.

Reporting Version For this version, we do the dual. We construct a data structure for 2d rectangle stabbing queries on the grid [1, ] 2 for the set of rectangles collected for all strings S ∈ G µ . By Lemma 6, for all µ groups, the whole preprocessing thus takes O(N i log N i ) time.

For every (T µ , T R µ ), we then ask the following queries: (x, y) is queried if and only if x is the rank of a leaf representing P [λ + 1 . . m -ρ] and y is the rank of a leaf representing P R [ρ + 1 . . m -λ]. For every (T µ , T R µ ), this takes O(m log N i ) time by Lemma 6 and by the fact that for each group G µ there are O(m) pairs (λ, ρ) such that m -(λ + ρ) = µ. For all groups G µ (they are at most m), all the queries thus take O(m 2 log N i ) time. Thus the total time for processing all G µ groups of segment i is O((m 2 + N i ) log N i ).

We are not done yet. By performing the above algorithm for active prefixes and active suffixes, we find out which pairs can be completed to a full occurrence of P with at most 1 error. This information is not sufficient to compute where such an occurrence ends (and storing additional information together with the active suffixes may prove costly). To overcome this, we use some ideas from the decision algorithm, appropriately modified to preserve the on-line nature of the reporting algorithm. Instead of iterating ρ over the lengths of precomputed active suffixes, we iterate it over all possible lengths in [0, m] (including 0 because we may want to include m in 1-AP i ). A suffix of P of length ρ completes a partial occurrence computed up to segment i exactly when m -ρ ∈ 1-AP i (a pair x ∈ 1-AP i , x + 1 ∈ AS i+1 corresponds to an occurrence). We thus use the reporting algorithm to compute the part of 1-AP i coming from the extension of AP i-1 (see Figure 2), and defer the reporting to the no-error version of the Prefix Case for the right j ; which was solved by Grossi et al. [START_REF] Grossi | On-line pattern matching on similar texts[END_REF] in linear time.

Prefix Case

Let T be an ED text and P be a pattern with a 1-error occurrence and an alignment in the Prefix Case with active prefix ending at T [i -1]. Let L = P [1 . . ]S , with ∈ AP i-1 , be a prefix of P that is extended in T [i] by S ; and Q be a suffix of P occurring in some string of T [i] (strings S , Q can be empty). By Lemma 2, we have 3 possibilities for any alignment of a 1-error occurrence of P in the Prefix Case:

1 mismatch: |L| + |Q| + 1 = m,
S is a prefix of the same string in which Q occurs, and they are one position apart (inspect Figure 3c).

deletion in

P : |L| + |Q| = m -1,
S is a prefix of the same string in which Q occurs, and they are consecutive.

1 insertion in P : |L| + |Q| = m, S is a prefix of the same string in which Q occurs, and they are one position apart.

For convenience, we only present the method for Hamming distance (1 mismatch). The other possibilities are handled similarly.

The techniques are similar to those for the Anchor Case (Section 3.2). We group the prefixes of all strings in T [i] according to their length µ ∈ [1, m). The total number of these prefixes is O(N i ). The group for length µ is denoted by G µ . We construct the compacted trie T Gµ of the strings in G µ , and the compacted trie T R Gµ of the reversed strings in G µ . This can be done in O(N i ) total time for all compacted tries. To achieve this, we employ the following lemma by Charalampopoulos et al. [START_REF] Charalampopoulos | Property suffix array with applications in indexing weighted sequences[END_REF]. (Recall that we have already sorted all letters of P . In what follows, we assume that N i ≥ m; if this is not the case, we can sort all letters of T

[i] in O(m + N i ) time.) Lemma 8 ([12]
). Let X be a string of length n over an integer alphabet of size n O (1) . Let I be a collection of intervals [i, j] ⊆ [1, n]. We can lexicographically sort the substrings X[i . . j] of X, for all intervals [i, j] ∈ I, in O(n + |I|) time.

We concatenate all the strings of T [i] to obtain a single string X of length N i , to which we apply, for each µ, Lemma 8, with a set I consisting of the intervals over X corresponding to the strings in G µ . By sorting, in this way, all strings in G µ (for all µ), and by constructing [START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF] and preprocessing [START_REF] Bender | The LCA problem revisited[END_REF] the generalized suffix tree of the strings in T [i] in O(N i ) time to support answering lowest common ancestor (LCA) queries in O(1) time, we can construct all T Gµ in O(N i ) total time. We handle T R Gµ , for all µ, analogously. Similar to the Anchor Case we enhance all nodes with a perfect hash table within the same complexities [START_REF] Michael | Storing a sparse table with 0(1) worst case access time[END_REF].

In contrast to the Anchor Case, we now only consider the set AP i-1 : namely, we do not consider AS i+1 . Let λ ∈ AP i-1 be the length of an active prefix. We treat every such element separately, and they are O(m) in total. Let µ = m-λ > 0 and consider the group G µ whose strings are all of length µ. The mismatch being at position h + 1 in one such string S determines a prefix S of S of length h that must extend the active prefix of P of length λ, and a fragment Q of S of length k = µ -h -1 that must match a suffix of P . We will consider all such pairs (h, k) whose sum is µ -1. The pairs are again (0, µ -1), (1, µ -2), . . . , (µ -1, 0), and there are clearly

O(µ) = O(m) of them.
Consider (h, k) as one such pair. We spell P [λ + 1 . . λ + h] in T Gµ . If the whole P [λ + 1 . . λ + h] is spelled successfully, this implies an interval of leaves of T Gµ corresponding to strings from T [i] that share

P [λ + 1 . . λ + h] as a prefix. We spell P R [1 . . k] in T R Gµ . If the whole P R [1 .
. k] is spelled successfully, this implies an interval of leaves of T R Gµ corresponding to strings from T [i] that have the same fragment (P R [1 . . k]) R . These two intervals form a rectangle in the grid implied by the leaves of T Gµ and T R Gµ . We need to check if these intervals both contain a leaf corresponding to the same prefix of length µ of a string in T [i]. If they do, then we have obtained an occurrence with 1 mismatch in T [i]. collect all p such that (p, q) ∈ Π and q ∈ [w 1 , x 1 ], and then search for these p in H: if for any p, H[p] = 1, then the answer is positive for p. Otherwise, we remove from H every p such that p ∈ [u 1 , v 1 ] and p / ∈ [u 2 , v 2 ] by setting H[p] = 0. We proceed by collecting all p such that (p, q) ∈ Π, q ∈ [w 2 , x 2 ] and q / ∈ [w 1 , x 1 ], and then search for them in H: if for any p, H[p] = 1, then the answer is positive for p. We repeat this until H is empty or until there are no other rectangles to process.

The whole procedure takes O(h + r) time, because we set at most h bits on in H, we set at most h bits back off in H, we search for at most h points in H, and then we process r rectangles.

Wrapping-up

To obtain Theorem 1 for the decision version of the problem we first compute AP i and AS i , for all i ∈ [1, n], in O(nm 2 + N ) total time (Corollary 3). We then compute all the occurrences in the Easy Cases using O(N ) time in total (Section 3.1); and we finally compute all the occurrences in the Prefix and Suffix Cases in i O(m 2 + N i ) = O(nm 2 + N ) total time (Lemma 11). Now, to solve the decision version of the problem, we solve the Anchor Cases with the use of the precomputed AP i-1 and

AS i+1 for each i ∈ [2, n -1] in O(m 2 √ log m + N i log log m) time (Section 3.
2), which gives O(nm 2 √ log m + N log log m) total time for the whole algorithm. For the reporting version we proceed differently to obtain an on-line algorithm; note that this is possible because we can proceed without AS i (see Figure 2). We thus consider one segment T [i] at the time, for each i ∈ [1, n], and do the following. We compute 1-AP i , as the union of three sets obtained from:

• The Suffix Case for T [i], computed in O(m 2 + N i ) time (Lemma 11).

• Standard APE with 1-AP i-1 as the input bit vector, computed in O(m 2 + N i ) time (Lemma 4).

• Anchor Case computed from AP i-1 in O((m 2 +N i ) log N i ) (Section 3.2) or O(m 3 +N i ) time (Lemma 9).
If N i ≥ m 3 , the algorithm of Lemma 9 works in the optimal O(m 3 + N i ) = O(N i ) time, hence we can assume that the O((m 2 + N i ) log N i )-time algorithm is only used when N i ≤ m 3 , and thus it runs in O((m 2 + N i ) log m) time. Therefore over all i the computations require O((nm 2 + N ) log m) or O(nm 3 + N ) total time. For every segment i we can also check whether an active prefix from 1-AP i-1 or from AP i-1 can be completed to a full match in T [i] using the algorithms of Grossi et al. from [START_REF] Grossi | On-line pattern matching on similar texts[END_REF] and Prefix Case, respectively, in O(m 2 + N i ) extra time.

By summing up all these we obtain Theorem 1.

with 1 mismatch by computing sets 1-AP i under Hamming distance, which, combined with the previously developed techniques, results in solving the 1-Mismatch EDSM problem in O(nm 2 + N log m) time.

Let us start with the following basic definition.

Definition 3 ([37]

). Let T be a rooted tree. The heavy path of T is the path that starts at the root and at each node descends to the child (called heavy node) with the largest number of leaf nodes in its subtree (ties are broken arbitrarily). The heavy-light decomposition of T is defined recursively as a union of the heavy path of T and the heavy path decompositions of the off-path subtrees of the heavy path. The nodes that are not heavy nodes are called light nodes (the root of T is always a light node). An edge on a heavy path is called heavy; and the other edges are called light.

A crucial property following from Definition 3 is that any root-to-leaf path crosses O(log |T |) paths. Each light edge on a path from the root decreases the size of the descending subtree by at least half. Thus the number of light edges on a path from any node to the root is O(log |T |).

We use the above properties to efficiently construct a tree T 1 (P, T [i]) (for a given ED text T [1 .

. n] of size N , a pattern P [1 . . m] and an index 1 ≤ i ≤ n with ||T [i]|| = N i ) in three steps (inspect Figure 5):

Step 1 We construct the compacted trie containing the strings in T [i] and suffixes P [j + 1 . . m] of P for each j ∈ AP i-1 . We call this set of suffixes of P act i-1 (P ). We also add labels (ι(X), #) to each node in the tree corresponding to a string X in act i-1 (P ) ∪ T [i], where ι(X) is a pointer to X and # is a special label. This takes O(m + N i ) time and space [START_REF] Farach | Optimal suffix tree construction with large alphabets[END_REF] (we add the suffixes of P in O(m) total time by constructing the suffix tree of P and truncating the superfluous suffixes). We call T 0 (P, T [i]) the tree we obtain from this step. In the next steps it will be extended with new nodes and labels to obtain T 1 (P, T [i]).

Step 2 We compute a heavy-light decomposition [START_REF] Daniel | A data structure for dynamic trees[END_REF] of T 0 (P, T [i]), which takes time linear in its size, namely O(m + N i ).

Step 3 For each light node u of T 0 (P, T [i]) let u be the leaf on the heavy path starting at u. Leaf u corresponds to a string X, and for each labeled descendant v of u outside of the heavy path u . . . u , if Y is the string corresponding to v, we compute p = 1 + LCP(X, Y ) (in O(1) time after linear-time preprocessing of the tree for LCA queries [START_REF] Bender | The LCA problem revisited[END_REF]) and add to T 1 (P, T [i]) the string obtained from Y by replacing Y [p] with X[p], with a label (ι(Y ), p) (a given node can store multiple labels). Intuitively, p is the position of a mismatch between (a prefix of) X and (a prefix of) Y . Since the tree T 0 (P, T [i]) has O(m + N i ) nodes and each of them has O(log(m + N i )) light node ancestors, there are no more than O((m + N i ) log(m + N i )) additional nodes and labels. Also the construction of new nodes can be done each time in O(1) time, because we in fact just copy a subtree of a light node and merge it with the subtree of its heavy sibling. We have thus arrived at the following lemma.

Lemma 12. The construction of T 1 (P, T [i]) takes O((m + N i ) log(m + N i )) time and space.

We now prove that the tree T 1 (P, T [i]) satisfies the following property.

Lemma 13. Let X ∈ act i-1 (P ). A string Y ∈ T [i] is at Hamming distance at most 1 from a prefix of X having length |Y | if and only if T 1 (P, T [i]) contains two nodes u, v respectively labeled by (ι(X), p) and (ι(Y ), p ), for some p, p ∈ N ∪ {#}, such that u is a descendant of v, and one of the following is satisfied:

• p = p ∈ N • p = # or p = #.
Proof. For the forward implication, if Y is a prefix of X then the claim is trivial since T 0 (P, T [i]) contains nodes with labels (ι(X), #) and (ι(Y ), #), and thus the first node is a descendant of the second one. Now, we assume that Y has one mismatch with X = X[1 . . |Y |] at a position p. Let u, v be nodes in T 0 (P, T [i]) respectively corresponding to X and Y , and let w be their lowest common light ancestor. Let Z be the string corresponding to the leaf on the heavy path starting at the heavy child of w. Since X and Y have a mismatch at position p, at least one of them has a mismatch with Z at position p and there are no mismatches to the left of p. Indeed, suppose towards a contradiction that there exists some p < p such that Z To prove the reverse implication, let us assume that the consequences are satisfied. Let u be the node whose label contains (ι(X), p) and v the node whose label contains (ι(Y ), p ). We first assume p = p ∈ N. Note that, by the construction of T 1 (P, T [i]), the node u (resp. v) corresponds to a string obtained by one letter modification on X (resp. on Y ) at the same position p. We denote the resulting string X (resp Ŷ ). Since v is an ancestor of u in T 1 (P, T [i]), Ŷ is a prefix of X. But this exactly means that Y has Hamming distance 1 with the length |Y | prefix of X (or Hamming distance 0 if both replacements replaced the same letter). If the second condition is satisfied, namely if p = # or p = #, then it means that one replacement in Y gives Ŷ which is a prefix of X, or that Y is a prefix of X, which is one replacement away from X, therefore we have the claimed result.

We next formalize how to find nodes satisfying one of the conditions from Lemma 13 and deduce the approximate active prefixes corresponding to the Anchor Case for segment T [i]. Let v 1 OR v 2 denote a bitwise OR of two vectors, and v 1 ⊕ x denote vector v 1 shifted by x positions to the right (the first x positions are set to 0).

  where by T [i][j] we denote the jth string of T [i]. (As an exception, we also add 1 to account for empty strings: if T

Theorem 1 .

 1 [i]. (It should be clear that for one alignment we may have multiple different i.) We show the following theorem. Given a pattern P of length m and an ED text T of length n and size N , the reporting version of 1-Error EDSM can be solved on-line in O(nm 2 log m + N log m) or O(nm 3 + N ) time. The decision version of 1-Error EDSM can be solved off-line in O(nm 2 √ log m + N log log m) time.

Theorem 2 .

 2 Given a pattern P of length m and an ED text T of length n and size N , 1-Mismatch EDSM can be solved on-line in O(nm 2 + N log m) or O(nm 3 + N ) time. Definition 2. For a string P = P [1 . . m], an ED string T = T [1] . . . T [n], a position 1 ≤ i ≤ n, and a distance on Σ * , we define three sets:

Lemma 3 .

 3 Given a pattern P = P [1 . . m] and an ED text T = T [1 . . n], a suffix P [j . . m] of P is an active suffix in T starting in the segment T [i] if and only if the prefix

Figure 2 :

 2 Figure 2: The layout of the algorithms for computing APi, 1-APi, and reporting occurrences. The green areas correspond to the (partial) matches in T [i], and the symbol * indicates the position of an error. The vertical bold lines indicate the beginning/the end of an occurrence or a 1-error occurrence. The cases without a label allow only exact matches and were already solved by Grossi et al. in [27].

Lemma 4 (

 4 [START_REF] Grossi | On-line pattern matching on similar texts[END_REF]). The APE problem for a string P of length m and a set S of strings of total length N can be solved in O(m 2 + N ) time. Given an algorithm for the APE problem working in f (m) + N time, we can find all active prefixes for a pattern P of length m in an ED text T = T [1] . . . T [n] of size N in O(nf (m) + N ) total time: Corollary 3 ([27]). For a pattern P of length m and an ED text T = T [1] . . . T [n] of total size N , computing the sets AP i for all i ∈ [1, n] takes O(nm 2 + N ) time.

1

  deletion in P : |L| + |Q| = m -1 and |S | + |S | = |S|. 1 insertion in P : |L| + |Q| = m and |S | + |S | + 1 = |S|.

  Charalampopoulos et al. have announced an improvement on the exponent of k from 4 to 3.5; specifically they presented an O( nk 3.5 √ log m log k m+ n)-time algorithm[START_REF] Charalampopoulos | Faster pattern matching under edit distance[END_REF].

Figure 4 :

 4 Figure 4: An example of points and rectangles (solid shapes) for the decision version of the Anchor Case with 1 mismatch. Here P = bbaaaabababb, APi-1 = {1, 2, 4, 7, 8, 9}, ASi+1 = {5, 6, 9, 11, 12}, µ = 3, and T [i] = {aaa, bba}. T3 and T R 3 are built for 4 strings: P [2 . . 4] = baa, P [3 . . 5] = aaa, P [8 . . 10] = aba, P [9 .. 11] = bab; the 5 rectangles correspond to pairs (ε, aa), (a, a), (aa, ε), (ε, ab), (b, a), namely, the pairs of prefixes and reversed suffixes of aaa and bba (rectangle (bb, ε) does not exist as T3 contains no node bb).

Lemma 11 .

 11 We can solve the Prefix (resp. Suffix) Case, that is, report 1-error occurrences ending in T [i] (resp. compute active prefixes with 1 error starting inT [i]) in O(m 2 + N i ) time.Proof. We employ Lemma 10 to get rid of the 2d range data structure. The key is that for every length-µ suffix P [λ + 1 . . m] of the pattern we can afford to pay O(µ + |G µ |) time plus the time to construct T Gµ and T R Gµ for set G µ . Because the grid is [1, |G µ |] 2 , we exploit the fact that the intervals found by spellingP [λ + 1 . . λ + µ -1] through T Gµ and P R [1 . . µ -1] through T R Gµ ,one letter at a time, are subset of each other, and querying µ such rectangles is done in O(µ + |G µ |) time by employing Lemma 10. Since we process at most m distinct length-µ suffixes of P , the total time is O(m 2 + N i ), because µ |G µ | ≤ N i .

Figure 5 :

 5 Figure 5: T0(P, T [i]) and T1(P, T [i]) for the example from Figure 4 (P = bbaaaabababb, APi-1 = {1, 2, 4, 7, 8, 9}, T [i] = {aaa, bba}) with labels (pj = ι(P [j . . m]), tj = ι( T [i][j])) and heavy paths.

  [p ] = X[p ](= Y [p ]): then the node corresponding to X[1 . . p ](= Y [1 . . p ]) would not be on the heavy path corresponding to Z, but would be a common ancestor of u and v, and thus w would not be the lowest common light ancestor of u and v, a contradiction. Assume first that X[p] = Z[p]. Then, there is a node with a label (ι(X), p) in the tree, which is a descendant of either v, having label (ι(Y ), #) (if Y [p] = Z[p]), or a node having label (ι(Y ), p) (if Y [p] = Z[p]), because we assumed that X and Y do not have any other mismatch. Finally, if X[p] = Z[p], then Y [p] = Z[p] and the node with label (ι(Y ), p) is an ancestor of u, having label (ι(X), #).

Proposition 5 .

 5 Algorithm 1 with input T 1 (P, T [i]) returns V res such that V res [p] = 1 if and only if p is an element of 1-AP i corresponding to the Anchor Case for segment T[i]. Algorithm 1 runs in O((m + N i ) log(m + N i ) + m 2 ) time.Proof. We first need the following remark:if P [1 . . k] extends into P [1 . . k ] in T [i], that means that some Y ∈ T [i] isat Hamming distance 1 from the prefix P [k + 1 . . k ] of P [k + 1 . . |P |]. Therefore, we are looking

Table 2 :

 2 The state of the art results for approximate EDSM and our new results for k = 1. Note that n ≤ G ≤ N . All algorithms underlying these results are combinatorial and all the reporting algorithms are on-line.

1-Mismatch EDSMIn this section, we give an alternative to the construction presented in Section 3.2, in the case of 1-Mismatch EDSM. We do so by finding matches in a tree containing both suffixes of P and elements from the segment T [i], as well as modified versions of those strings. The number of additional strings is bounded by using the heavy-light decomposition of Sleator and Tarjan[START_REF] Daniel | A data structure for dynamic trees[END_REF]. The construction is directly inspired by the one presented by Thankachan et al. in[START_REF] Sharma | A provably efficient algorithm for the k -mismatch average common substring problem[END_REF], which is itself inspired by the k-errata tree construction introduced by Cole et al. in[START_REF] Cole | Dictionary matching and indexing with errors and don't cares[END_REF] for indexing with errors. We give an algorithm to find all occurrences of P in T

The work in this paper is supported in part by: the Netherlands Organisation for Scientific Research (NWO) through project OCENW.GROOT.2019.015 "Optimization for and with Machine Learning (OPTIMAL)" and Gravitation-grant NETWORKS-024.002.003; the PANGAIA and ALPACA projects that have received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreements No 872539 and 956229, respectively; and the MUR -FSE REACT EU -PON R&I 2014-2020.

all such pairs of positions (h, k) whose sum is µ -1 (intuitively, the minus one is for the mismatch). This guarantees that L = P [1 . . λ]S and Q = S P [m -ρ + 1 . . m] are such that |L| + |Q| + 1 = m. pairs are (0, µ-1), (1, µ-2), . . . , (µ-1, 0). This guarantees that L and Q are one position apart

The number of these pairs is O(µ) = O(m). Consider one such pair (h, k) and a string S ∈ G µ . We treat every such string S separately. We spell S[1 . . h] in T µ . If the whole S[1 . . h] is successfully spelled ending at a node u, this implies that all the fragments of P corresponding to nodes descending from u share S[1 . . h] as a prefix. We also spell

. k] is successfully spelled ending at a node v, then all the fragments of P corresponding to nodes descending from v share (S R [1 . . k]) R as a suffix. Nodes u and v identify an interval of leaves in T µ and T R µ , respectively. We need to check if these intervals both contain a leaf corresponding to the same fragment of P . If they do, then we obtain an occurrence of P with 1 mismatch (see Figure 4). We now have two different ways to proceed, depending on whether we need to solve the off-line decision version or the on-line reporting version.

Decision Version Let us recall that T µ , T R µ by construction are ordered based on lexicographic ranks. For every pair (T µ , T R µ ), we construct a data structure for 2d rectangle emptiness queries on the grid [1, ] 2 , where is the number of leaves of T µ (and of T R µ ), for the set of points (x, y) such that x is the lexicographic rank of the leaf of T µ representing P [λ + 1 . . m -ρ] and y is the rank of the leaf of T R µ representing

To do this we construct, for every (T Gµ , T R Gµ ), a 2d range data structure for the set of points (x, y) such that x is the rank of a leaf of T Gµ , y is the rank of a leaf of T R Gµ , and the two leaves correspond to the same prefix of length µ of a string in T [i]. For every (T Gµ , T R Gµ ), this takes O(|G µ | log |G µ |) time by Lemma 5. For all G µ groups, the whole preprocessing takes O(N i √ log N i ) time. We then ask 2d range emptiness queries each taking O(log log |G µ |) time by Lemma 5. Note that all rectangles for λ can be collected in O(m) time by spelling

Gµ , one letter at a time. This gives a total of O(m 2 log log

To solve the Suffix Case (compute active prefixes with 1 error starting in T [i]) we employ the mirror version of the algorithm, but iterating λ over the whole [0, m] instead of AS i+1 (like in the reporting version of the Anchor Case).

Shaving Logs using Special Cases of Geometric Problems

Proof. By Lemma 6, 2d rectangle stabbing queries can be answered in O(log n) time using O(n log n) space after O(n log n)-time preprocessing.

Notice that in the case of the 2d rectangle stabbing used in Section 3.2 the rectangles and points are all in a predefined [1, m] × [1, m] grid. In such a case we can also use an easy folklore data structure of size O(m 2 ), which after an O(m 2 + |rectangles|)-time preprocessing answers such queries in O(1) time.

Namely, the data structure consists of a [1, m + 1] 2 grid Γ (a 2d-array of integers) in which for every rectangle

Then we modify Γ to contain the 2d prefix sums of its original values (we first compute prefix sums of each row, and then prefix sums of each column of the result). After these modifications, Γ[x][y] stores the number of rectangles containing point (x, y), and hence after O(m 2 + |rectangles|)-time preprocessing we can answer 2d rectangle stabbing queries in O(1) time.

In our case we have a total of O(m) such grid structures, each of O(m 2 ) size, and ask O(m 2 ) queries, and hence obtain an O(m 3 + N i )-time and O(m 2 )-space solution for computing 1-AP i from AP i-1 .

Prefix Case: a Special Case of 2d Rectangle Stabbing

Inspect the example of Figure 4 for the Anchor Case. Note that the groups of rectangles for each string have the special property of being composed of nested intervals: for each dimension, the interval corresponding to a given node is included in the one corresponding to any of its ancestors. Thus for the Prefix Case, where we only spell fragments of the same string P in both compacted tries, we consider the following special case of off-line 2d rectangle stabbing. Lemma 10. Let p 1 , . . . , p h and q 1 , . . . , q h be two permutations of [1, h]. We denote by Π the set of h points (p 1 , q 1 ), (p 2 , q 2 ), . . . , (p h , q h ) on [1, h] 2 .

Further let R be a collection of r axis-aligned rectangles

Then we can find out, for every point from Π, if it stabs any rectangle from R in O(h + r) total time.

Proof. Let H be a bit vector consisting of h bits, initially all set to zero. We process one rectangle at a time. We start with ([u 1 , v 1 ], [w 1 , x 1 ]). We set H[p] = 1 if and only if (p, q) ∈ Π for p ∈ [u 1 , v 1 ] and any q. We Algorithm 1 Search(T )

1: Global variables: the set act i-1 (P ), a segment T [i], and bit vectors V # , V 1 , . . ., V m , V AN Y , V res all of size |P | + 1, and initially set to all 0's 2: Input: T -a subtree of T 1 (P, T [i]) with root r 3: Output: represented by global bit vector V res 4: for each label (ι(X), p) with X ∈ T [i] on r do

10: for each T a subtree of T rooted at a child of r do 11:

run Search(T )

for the pairs described in Lemma 13. We show then that V res [k ] = 1 after the end of the procedure if and only if there is a pair of nodes u, v in T 1 (P, T [i]) satisfying the conditions of Lemma 13 for

Let us assume the existence of such a pair (u, v). Since the tree is traversed in a DFS, the node v (with a label (ι(Y ), p ), p ∈ N ∪ {#}) is traversed before u, which is its descendant; and at this moment,

Since u is a descendant of v, the vectors are not modified at position |Y | until u is visited: that would mean that v has a strict descendant representing a string of the same length as the string represented by v. When the label (ι(X), p) for X ∈ act i-1 (P ) is visited on u, we set the position (m -|X|)

Vice versa, if after the processing one has V res [k ] = 1, this means that at some point in the DFS a node u having a label (ι(X), p) with X ∈ act i-1 (P ) and p ∈ N ∪ # was visited, and that at this point, for k = m -|X|, one had V AN Y [k -k] = 1 or V p [k -k] = 1 for (p, p ) satisfying the conditions from Lemma 13. This one had to be set previously in the DFS at a node v having label (ι(Y ), p ) for Y ∈ T [i] with |Y | = k -k. Finally, an ancestor of u can be chosen as such v, because otherwise, from the DFS traversal order, the corresponding component of the vectors would have been set to 0. Now, the pair of nodes (u, v) satisfy the conditions of Lemma 13, and from our observations that means that there is an active prefix with 1 error of P having length k, extending up to T [i].

The running time follows from the fact that the algorithm visits only O((m + N i ) log(m + N i )) labels by Lemma 12, and from the fact that the tree is traversed in a DFS. The analysis of each label consists in reading it and doing a constant number of bit modifications in the stored vectors, and, for O(m log(m + N i )) of them (the one corresponding to a suffix of P ), doing an OR operation which takes O( m log(N +m) ) time in the word RAM model. This gives us the required running time. Proof. We proceed in the same way as in the reporting version of Section 3.5; the only difference is that, when N i ≤ m 3 , to extend AP i-1 into 1-AP i , instead of using the O((m 2 + N i ) log m)-time algorithm, we use the one from Proposition 5. Due to this change, the algorithm runs in the desired time. Indeed, notice that when N i ≤ m 3 , O((N i +m) log(m+N i )+m 2 ) = O(N i log m+m 2 ), and when N i ≥ m 3 , O(m 3 +N i ) = O(N i ). The total time is thus O(nm 2 + N log m).

Open Questions

While our techniques (Sections 3 and 4) seem to generalize relatively easily to k errors, they would incur some exponential factor with respect to k. We leave the following basic questions open:

1. Can we design an O(nm 2 + N )-time algorithm for 1-EDSM under edit or Hamming distance? 2. Can our techniques be efficiently generalized for k > 1 errors or mismatches? 3. Can our Hamming distance improvement for 1 mismatch (Section 4) be extended to edit distance?


Activation Sites Estimation using a Fast Algorithm

Based on an Eikonal Equation J érôme Fehrenbach, Lisl Weynans --Univ. Toulouse, IMT and Univ. Bordeaux, Inria, IHU Liryc, France

Context and objectives

Classical algorithms for ECGI solve at each time instant an static and extremely ill-posed inverse problem, requiring an adequate regularization strategy (or instance Tikhonov) An alternative way of regularizing the inverse problem is to consider information from other time steps, taking into account that electric potentials in the heart are obtained by the propagation of an electric wave. Our objectives: design a fast algorithm based on a simple activation front model to retrieve significant features of the ECGI inverse problem

Propagation model

We consider in the present work only the surface of the heart Anisotropic eikonal equation: simplified model of electrical activation front in asymptotic regime:

∇T D(x) = , T(x i ) = τ i , i = . . . s,

Test case: mimicking an ECG inversion

Conclusion

Efficient new method to estimate sources and activation times in the eikonal equation on a surface ⇒ applicable to ECGI. In case of complex or pathological propagation patterns, need to extend the method to a cardiac volume.

  Figure: Example of solution of eikonal equation with anisotropic conduction

Figure

  Figure: Left: location of the successive iterates x k (red) and the true source point x * (blue). Right: evolution of the parameters of the metric.

Figure :

 : Figure: Left: configuration of the torso (electrodes in red) and the heart surface (visible by transparency). Right: location of the successive iterates x k (red) and the true source point x * (blue)