**Observation 7.3.** Let $ed_{i-1}(r')$ be the smallest edit distance from $P_{i-1}$ to a suffix of $T[1..r']$, and define

$$d = \min_{\substack{r' \in \mathbf{OCC}_k^E(P_{i-1}, T) \\ r' \in [r+1-\Delta_i, r+1-\Delta_i+2k]}} \{\mathbf{ed}_{i-1}(r') + \mathbf{ed}(P[\ell_{i-1}+1..\ell_i], T[r'+1..r])\} \quad (2)$$

The smallest edit distance from $P_i$ to $T[1..r]$ is equal to $d$ if $d \le k$ and is larger than $k$ otherwise.

It follows that to decide whether $r \in \mathbf{OCC}_k^E(P_i, T)$, it suffices to compute the value $\min\{d, k+1\}$, where $d$ is as defined above.

**Case 2:** $P_{i-1}$ is not k-periodic. In this case, $\mathbf{OCC}_k^E(P_{i-1}, T)$ is stored as $\mathcal{O}(k^3)$ chains of size one. Therefore, we can find the positions $r'$ from Eq. (2) in $\mathcal{O}(k^3)$ time. Moreover, for each position $r'$, we run the dynamic programming algorithm for $T[r'+1..]$ and $P[\ell_{i-1}+1..\ell_i]$, which outputs the edit distance between $T[r'+1..r]$ and $P[\ell_{i-1}+1..\ell_i]$ if it is at most $k$. As we also know the smallest edit distance between $P_{i-1}$ and a suffix of $T[1..r']$, we can compute $d$ in $\mathcal{O}(k^3)$ time.

**Case 3:** $P_{i-1}$ and $P_i$ are k-periodic. We can identify all positions $r'$ from Eq. (2) in $\mathcal{O}(k^3)$ time. (It suffices to check each of the $\mathcal{O}(k^3)$ chains that we store for $P_{i-1}$). We must now test each of these positions. Consider a position $r'$ and let $C$ be the chain containing it. It suffices to compute the edit distance between $P[\ell_{i-1}+1..\ell_i]$ and $T[r'+1..r]$ as we already know the smallest edit distance from $P_{i-1}$ to a suffix of $T[1..r']$. If $|C| = 1$, the distance has been computed by the dynamic programming algorithm. Otherwise, we use quasi-greedy encodings. On a high level, our goal is to compute the edit distance between $\pi = P[\ell_{i-1}..\ell_i]$ and $\tau = T[r'+1..r]$ via a string $\mu = D^\infty[1..\Delta_i]$, where $D$ is the difference of $C$ and $\Delta_i = \ell_i - \ell_{i-1} + k$.

**Lemma 7.4.** There is $\mathbf{ed}(\pi, \mu) \le 26k$.

*Proof.* As $P_{i-1}$ and $P_i$ are k-periodic, by Claim 7.1 we obtain that $P_i = P[1..\ell_i]$ is k-periodic with k-period $Q_i = Q_{i-1}$, that is, there is a prefix of $Q_i^\infty$ such that the edit distance between it and $P_i$ is at most $2k$. By Fact 2.3, there is a substring $Q_i^\infty[r..t]$ such that $|r - \ell_{i-1}| \le 2k$ and $|t - \ell_i| \le 2k$ and $\mathbf{ed}(Q_i^\infty[r..t], \pi) \le 2k$. By the triangle inequality, we obtain that $\mathbf{ed}(Q_i^\infty[\ell_{i-1}+1..\ell_i], \pi) \le 6k$. Let $a = \ell_{i-1} - 7k \pmod{q_i}$ and $b = \ell_{i-1} + 7k \pmod{q_i}$. By Corollary 3.5, $D$ is a rotation of $Q_{i-1} = Q_i$ with shift $\Delta$, where $\Delta \in [a-3k, b+3k]$ if $a \le b$ and $\Delta \in [0, b+3k] \cup [a-3k, q_i)$ if $a > b$. It follows that $D^\infty = Q_i^\infty[s..]$, where $|s - \ell_{i-1}| \le 10k$. As $\mu = D^\infty[1..\Delta_i] = Q_i^\infty[s..s+\Delta_i-1]$, by the triangle inequality we obtain $\mathbf{ed}(\mu, Q_i^\infty[\ell_{i-1}+1..\ell_i]) \le 20k$. Applying the triangle inequality one more time, we obtain the claim. $\square$

Let $\mathcal{G}_P = \mathbf{qGR}_{30k}(\pi, \mu)$ and $\mathcal{G}_T = \mathbf{qGR}_{30k}(\mu, \tau)$. By Corollary 5.27, knowing $\mathcal{G}_P$ and $\mathcal{G}_T$ is sufficient to compute the edit distance between $\pi$ and $\tau$. Note that we do not know $\mathcal{G}_T$ yet, we must compute it using the available information. Let $p$ be the rightmost position in $C$.

1. Recall that at the position $(p+1)$ we launched an algorithm that is computing $\mathbf{qGR}_{32k}(T[p+1..p+\Delta_i], D^\infty[1..\Delta_i])$ with a delay of $k$ characters (Corollary 5.22). We have $p + \Delta_i \ge r' + \Delta_i \ge r$. Therefore, upon reaching $r$, we can use the memory of the algorithm to compute $\mathcal{G}_{T,1} = \mathbf{qGR}_{32k}(T[p+1..r], D^\infty[1..r-p])$ in $\tilde{\mathcal{O}}(k^5)$ time and $\tilde{\mathcal{O}}(k^2)$ space (Lemma 5.21).

2. By the definition of chains, $T[r' + 1..p] = D^j$ for some integer $j$. By Lemma 5.21, we can use $\mathbf{qGR}_{32k}(D, D)$ computed during the preprocessing step to compute $\mathcal{G}_{T,2} = \mathbf{qGR}_{32k}(T[r' + 1..p], D^j)$ in $\tilde{\mathcal{O}}(k^5)$ time and $\tilde{\mathcal{O}}(k^2)$ space. By applying Lemma 5.21 again, we can compute $\mathbf{qGR}_{32k}(T[r' + 1..p], D^jD^\infty[1..r-p])$ in $\tilde{\mathcal{O}}(k^5)$ time and $\tilde{\mathcal{O}}(k^2)$ space.
3. Finally, we compute via Corollary 5.22 the encoding $qGR_{30k}(\varepsilon, D^\infty[r-p+1..\Delta_i])$, where $\varepsilon$ is the empty string and $\Delta_i - (r-p) \le 2k$. We then apply Observation 5.20 to compute $qGR_{30k+(\Delta_i-(r-p))}(T[r'+1..p], D^jD^\infty[1..r-p])$ and further Lemma 5.21 to compute $qGR_{30k}(T[r'+1..p], D^\infty[1..\Delta_i]) = \mathcal{G}_T$.

**Updating the chains.** When we detect a new $k$-edit occurrence of $P_i$, we must decide if it should be added to some existing chain or if we must create a new chain for this occurrence.

To this end, for each $1 \le i \le z$, we consider $O(k)$ of its rotations of $Q_i$ that can be the difference of a chain of $k$-edit occurrences of $P_i$ in $T$ (Corollary 3.5). For each rotation $R$, we run a constant-space and linear-time deterministic pattern matching algorithm [54]. The algorithm processes the text $T$ as a stream and if there is an occurrence $T[\ell..r]$ of the rotation reports it while reading $T[r]$. The algorithm uses $O(1)$ space and $O(1)$ amortised time per character of $T$.

Suppose that we detect a new right endpoint $r$ of a $k$-edit occurrence $T[\ell..r]$ of $P_i$. We must decide whether $r$ belongs to an existing chain of $k$-edit occurrences of $P_i$ or starts a new one. In order to do this, we first find the chain $C$ that contains $r - q_i + 1$ if it exists by checking each chain in turn. We then check that the smallest edit distance from a suffix of $T[1..r]$ to $P_i$ equals to $\text{ed}(C)$ and that $T[r - q_i + 1..r]$ is equal to the difference of the chain. (Recall that we run the exact pattern matching algorithm for each rotation of $Q_i$ that can be the difference of a chain so that both checks can be performed in $O(1)$ time).

If these conditions are not satisfied, we create a new chain that contains $r$ only. Otherwise, we add $r$ to $C$ (i.e., increment the size of $C$). To finalize the update of the chains, we must delete all $k$-edit occurrences that become inactive: for each $i$ and for each chain of $k$-edit occurrences of $P_i$, we “delete” the first $k$-edit occurrence if it starts before $r - \ell_i - k + 1$. To “delete” a $k$-edit occurrence, we simply update the endpoints of the first occurrence in the chain and the total number of occurrences in the chain.

### 7.2.3 Analysis

We summarize the results of this section:

**Theorem 7.5.** *Assume a read-only pattern P of length m and a streaming text T of length n. There is a deterministic algorithm that finds the set $\text{OCC}_k(P, T)$ using $\tilde{O}(k^5)$ space and $\tilde{O}(k^6)$ amortised time per character of the text T.*

*Proof.* Let us first upper bound the space complexity of the algorithm. For each $i = 1, \dots, z = O(\log m)$, we store the set $\mathbf{aOCC}_k(P_i, T)$ as $O(k^3)$ chains. For each chain, we launch the dynamic programming algorithm (Fact 7.2), which takes $\tilde{O}(k^2)$ space and Corollary 5.22 that takes $\tilde{O}(k^2)$ space. The pattern matching algorithms for the rotations of $Q_i$ take $\tilde{O}(k)$ space in total. Finally, testing if a position of the text is the rightmost position of a $k$-edit occurrence of $P_i$ requires $\tilde{O}(k^2)$ space.

We now show the time bound. Updating the chains takes $\tilde{O}(1)$ time. At any time, we run $\tilde{O}(k^3)$ instances of Corollary 5.22 that takes $O(k^3)$ amortised time per character. To test each position $r$, we spend $\tilde{O}(k \cdot k^3)$ time. $\square$

## 7.3 Streaming Algorithm

We now modify the algorithm for the semi-streaming model to develop a fully streaming algorithm. W.l.o.g., assume $k \le m$ and take $\delta = 1/n^c$ for $c$ large enough.
### 7.3.1 Preprocessing

We define the prefixes $P_i$ and their periods $Q_i$ exactly in the same way as in Section 7.2. Recall that $\ell_i = |P_i|$ and $q_i = |Q_i|$. For every $i > 1$, we store the following information, where all sketches $\text{sk}^q$ (Corollary 6.23) are parametrized by probability $\delta$, maximal length $\Delta_i$, the alphabet of $P$ and $T$, and a seed of $\mathcal{O}(\log^2 n \log(1/\delta))$ random bits:

1. $P[\ell_i]$ and the sketch $\text{sk}_k^q(P[\ell_{i-1} \dots \ell_i])$;

2. For each of rotation $D$ of $Q_i$ that can be a difference of a chain of $k$-edit occurrences of $P_i$, the encoding $\text{qGR}_{30k}(P[\ell_{i-1} + 1 \dots \ell_i], D^\infty[1 \dots \Delta_i])$, where $\Delta_i = \ell_i - \ell_{i-1} + k$;

3. For each of rotation $D$ of $Q_i$ that can be a difference of a chain of $k$-edit occurrences of $P_i$, the sketches $\text{sk}_{32k}^q(D)$ and $\text{sk}_{32k}^q(D[1 \dots \Delta_i (\text{mod } q_i)])$.

### 7.3.2 Main Stage

As in Section 7.2, for each $i$, we store $\text{aOCC}_k^E(P_{i-1}, T)$ in $\mathcal{O}(k^3)$ chains. For each chain $C$, we store the leftmost position $lp$ in it, its size $|C|$, and the smallest edit distance, $\text{ed}(C)$, from a suffix of $T[1 \dots lp]$ to $P_{i-1}$. If $|C| \ge 2$, we also store its difference (defined by the shift of the rotation of $Q_{i-1}$).

If $p^*$ is the first position added to $C$, then at the position $(p^* + 1)$, we start running the streaming algorithm of Corollary 6.23(a) for computing the sketch $\text{sk}_k^q(T[p^a st + 1 \dots p^a st + \Delta_i])$.

Furthermore, consider the moment when we detect the second position in $C$ (if it exists) and hence the difference $D$ of the chain. Starting from this moment, for every newly added position $p \in C$, at the position $(p+1)$ we start computing the quasi-greedy encoding $\text{qGR}_{32k}(T[p+1 \dots p + \Delta_i], D^\infty[1 \dots \Delta_i])$ as follows: Assume that we have computed $\text{qGR}_{32k}(T[p+1 \dots p + \ell \cdot q_i], D^\infty[1 \dots \ell \cdot q_i])$. Suppose first that $(\ell+1) \cdot q_i \le \Delta_i$. While reading $T[p+\ell \cdot q_i+1 \dots p+(\ell+1) \cdot q_i]$, we compute $\text{sk}_{32k}^q(T[p+\ell \cdot q_i+1 \dots p+(\ell+1) \cdot q_i])$ again via the algorithm of Corollary 6.23(a). We then use this sketch and $\text{sk}_{32k+1}^q(D)$ to compute $\text{qGR}_{32k}(T[p+\ell \cdot q_i+1 \dots p+(\ell+1) \cdot q_i], D)$ (Corollary 6.23(b)) and then $\text{qGR}_{32k}(T[p+1 \dots p+(\ell+1) \cdot q_i], D^\infty[1 \dots (\ell+1) \cdot q_i])$ (Lemma 5.21). If $(\ell+1) \cdot q_i > \Delta_i$, we use the sketches $\text{sk}_{32k}^q(T[p+\ell \cdot q_i \dots p+\Delta_i])$ and $\text{sk}_{32k}^q(D[1 \dots \Delta_i (\text{mod } q_i)])$, the rest is analogous. We continue running the algorithm until either the computation is completed or a new $k$-edit occurrence in the chain has been detected. In other words, in the end we compute the encoding for the rightmost position in the chain.

**Detecting new $k$-edit occurrences of $P_i$.** We now explain how we modify the algorithm for detecting new $k$-edit occurrences of the prefixes $P_i$. The algorithm for Case 1 does not change. Instead of the dynamic programming algorithm in Case 2, we use $\text{sk}_k^q$ and use Corollary 6.23(b) and then Corollary 5.27 to compute the edit distance. It remains to explain how we modify the algorithm for Case 3.

We exploit Eq. (2) again. We can find all positions $r'$ in $\mathcal{O}(k^3)$ time. To test a position $r'$, it suffices to compute the edit distance between $P[\ell_{i-1} + 1 \dots \ell_i]$ and $T[r' + 1 \dots r]$. Let $C$ be the chain with difference $D$ that contains $r'$. If $|C| = 1$, we use the edit distance sketch, and otherwise the quasi-greedy encodings. By Lemma 7.4, $\text{ed}(P[\ell_{i-1} \dots \ell_i], D^\infty[1 \dots \Delta_i]) \le 26k$ and hence by Corollary 5.27, the edit distance between $P[\ell_{i-1} + 1 \dots \ell_i]$ and $T[r' + 1 \dots r]$ can be computed from the encodings $\mathcal{G}_P = \text{qGR}_{30k}(\pi, \mu)$ and $\mathcal{G}_T = \text{qGR}_{30k}(\mu, \tau)$ for $\pi = P[\ell_{i-1} \dots \ell_i]$, $\mu = D^\infty[1 \dots \Delta_i]$, and $\tau = T[r' + 1 \dots r]$. $\mathcal{G}_P$ was computed during the preprocessing step and we store it explicitly. Hence, we only need to explain how to compute $\mathcal{G}_T$. Let $p$ be the rightmost position in the chain $C$.

1. Recall that $T[r' + 1 \dots p] = D^j$ for $j = (p - r')/q_i$. We first compute $\text{qGR}_{32k}(D, D)$ from $\text{sk}_{32k}^q(D, D)$ via Corollary 6.23(b), and then $\mathcal{G}_{T,1} = \text{qGR}_{32k}(T[r' + 1 \dots p], D^j) =$
$q\mathbf{GR}_{32k}(D^j, D^l)$ in $\tilde{O}(k^5)$ time and $\tilde{O}(k^2)$ space as in Section 7.2.

2. At the position $(p+1)$ we launched the streaming algorithm computing $q\mathbf{GR}_{32k}(T[p+1..p+\Delta_i], D^\infty[1..\Delta_i])$ with a delay of $q_i$ characters. We have $p+\Delta_i \ge r'+\Delta_i \ge r$. Therefore, at a position $p+\ell \cdot q_i$, where $\ell = \lfloor (r-p+1)/q_i \rfloor$, the algorithm computes $G_{T,2} = q\mathbf{GR}_{32k}(T[p+1..p+\ell \cdot q_i], D^\infty[1..\ell \cdot q_i])$. The algorithm then continues to compute the sketch $\mathbf{sk}_{32k}^q(T[p+\ell \cdot q_i+1..r])$. We use this sketch and the sketch $\mathbf{sk}_{32k}^q(D[1..\Delta_i \pmod{q_i}])$ to compute $G_{T,3} = q\mathbf{GR}_{30k}(T[p+\ell \cdot q_i+1..r], D[1..\Delta_i \pmod{q_i}])$ via Corollary 6.23(b) and Observation 5.20.

3. We finally concatenate $G_{T,1}$ and $G_{T,2}$ to obtain $q\mathbf{GR}_{32k}(T[r'+1..r'+(\ell+j) \cdot q_i], D^\infty[1..(\ell+j) \cdot q_i])$, and then $q\mathbf{GR}_{32k}(T[r'+1..r'+(\ell+j) \cdot q_i], D^\infty[1..(\ell+j) \cdot q_i])$ and $G_{T,3}$ to obtain $G_T$ via Lemma 5.21 (note that the difference of lengths of strings in $G_{T,3}$ is bounded by $2k$).

**Updating the chains.** When we detect a new $k$-edit occurrence of $P_i$, we must decide if it should be added to some existing chain or if we must create a new chain for this occurrence. We use the algorithm of Section 7.2, but replace the constant-space pattern matching algorithm with the streaming pattern matching algorithm [52] that for a rotation of $Q_i$ takes $\tilde{O}(1)$ space and $\tilde{O}(1)$ time per character and retrieves all its occurrences correctly with probability at least $1-\delta$.

### 7.3.3 Analysis

We summarize the results of this section:

**Theorem 7.6.** Given a pattern $P$ of length $m$ and a text $T$ of length $n$. There is a streaming algorithm that finds the set $\text{OCC}_k^E(P, T)$ using $\tilde{O}(k^5)$ space and $\tilde{O}(k^8)$ amortised time per character of the text $T$. The algorithm computes $\text{OCC}_k^E(P, T)$ correctly with high probability.

*Proof.* By Corollary 3.5, for a fixed $i$ only $O(k)$ rotations of $Q_i$ can be a difference of a chain of occurrences of $P_i$. The sketch $\mathbf{sk}_{30k+1}^q(\cdot)$ takes $\tilde{O}(k^2)$ space (Corollary 6.23(a)) and $q\mathbf{GR}_{30k}(\cdot, \cdot)$ $\tilde{O}(k^2)$ space as well (Corollary 5.17). Therefore, the information computed during the preprocessing stage occupies $\tilde{O}(k^3)$ space. During the main stage, we store $\tilde{O}(k^3)$ chains. For each chain, we run the algorithm of Corollary 6.23(a) that takes $\tilde{O}(k^2)$ space. The algorithm then computes the quasi-greedy encoding (Corollary 6.23(b)) takes $\tilde{O}(k^2)$ space as well. In total, the information we store for the chains occupies $\tilde{O}(k^5)$ space. When checking for new occurrences, we apply Lemma 5.21 and Corollary 5.27, which require an overhead of $\tilde{O}(k^2)$ space. Finally, the streaming pattern matching algorithms for the rotations of $Q_i$ that can be differences of occurrences of $P_i$ take $\tilde{O}(k)$ space in total. The space bound follows.

At any time, we run $\tilde{O}(k^3)$ instances of the algorithm of Corollary 6.23(a) that takes $\tilde{O}(k)$ amortised time per character. In addition, for every character we run $\tilde{O}(k^3)$ instances of the algorithms of Lemma 5.21 and Corollary 5.27 taking $\tilde{O}(k^8)$ time in total. The pattern matching algorithms for the rotations of $Q_i$ take $\tilde{O}(k)$ time per character.

Note that the only probabilistic procedures in the algorithm are streaming pattern matching [52] and that of Corollary 6.23(b) that computes quasi-greedy encodings. These procedures are called $\text{poly}(n, k) = \text{poly}(n)$ times. By choosing the constant $c$ in $\delta = 1/n^c$ large enough, we can guarantee that the algorithm is correct with high probability by the union bound. $\square$
## References

[1] Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends: Or: A polylog shaved is a lower bound made. In *STOC 2016*, pages 375–388, 2016.

[2] Karl R. Abrahamson. Generalized string matching. *SIAM J. Comput.*, 16(6):1039–1051, 1987. doi:10.1137/0216067.

[3] Amihood Amir, Moshe Lewenstein, and Ely Porat. Faster algorithms for string matching with *k* mismatches. *Journal of Algorithms*, 50(2):257–275, 2004. URL: https://doi.org/10.1016/S0196-6774(03)00097-X, doi:10.1016/S0196-6774(03)00097-X.

[4] Ajesh Babu, Nutan Limaye, Jaikumar Radhakrishnan, and Girish Varma. Streaming algorithms for language recognition problems. *Theor. Comput. Sci.*, 494:13–23, 2013.

[5] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In *STOC 2015*, pages 51–58, 2015. doi:10.1145/2746539.2746612.

[6] Djamal Belazzougui and Qin Zhang. Edit distance: Sketching, streaming, and document exchange. In *FOCS 2016*, pages 51–60, 2016. doi:10.1109/FOCS.2016.15.

[7] Dany Breslauer and Zvi Galil. Real-time streaming string-matching. *ACM Trans. Algorithms*, 10(4):22:1–22:12, 2014. doi:10.1145/2635814.

[8] Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In *FOCS 2015*, pages 79–97, 2015. doi:10.1109/FOCS.2015.15.

[9] Diptarka Chakraborty, Debarati Das, and Michal Koucký. Approximate online pattern matching in sublinear time. In *FSTTCS 2019*, volume 150 of *LIPIcs*, pages 10:1–10:15, 2019. doi:10.4230/LIPIcs.FSTTCS.2019.10.

[10] Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký. Streaming algorithms for embedding and computing edit distance in the low distance regime. In *STOC 2016*, pages 712–725, 2016. doi:10.1145/2897518.2897577.

[11] Timothy M. Chan, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat. Approximating text-to-pattern Hamming distances. In *STOC 2020*, pages 643–656, 2020. URL: https://doi.org/10.1145/3357713.3384266, doi:10.1145/3357713.3384266.

[12] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz. Faster approximate pattern matching: A unified approach. In *FOCS 2020*, pages 978–989, 2020. doi:10.1109/FOCS46700.2020.00095.

[13] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya. Dictionary matching in a stream. In *ESA 2015*, volume 9294 of *LNCS*, pages 361–372, 2015. doi:10.1007/978-3-662-48350-3_31.

[14] Raphaël Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya. The *k*-mismatch problem revisited. In *SODA 2016*, pages 2039–2052, 2016. doi:10.1137/1.9781611974331.ch142.
[15] Raphaël Clifford, Markus Jalsenius, and Benjamin Sach. Cell-probe bounds for online edit distance and other pattern matching problems. In *SODA 2015*, pages 552–561, 2015. doi:10.1137/1.9781611973730.37.

[16] Raphaël Clifford, Tomasz Kociumaka, and Ely Porat. The streaming k-mismatch problem, 2019. doi:10.1137/1.9781611975482.68.

[17] Richard Cole and Ramesh Hariharan. Approximate string matching: A simpler faster algorithm. *SIAM J. Comput.*, 31(6):1761–1782, 2002. doi:10.1137/S0097539700370527.

[18] Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou. Streaming periodicity with mismatches. In *APPROX 2017*, pages 42:1–42:21, 2017.

[19] Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, and Samson Zhou. Periodicity in data streams with wildcards. In *CSR 2018*, pages 90–105, 2018. doi:10.1007/978-3-319-90530-3_9.

[20] Funda Ergün, Hossein Jowhari, and Mert Sağlam. Periodicity in streams. In *APPROX 2010*, pages 545–559, 2010. doi:10.1007/978-3-642-15369-3\_41.

[21] N. François, F. Magniez, M. de Rougemont, and O. Serre. Streaming property testing of visibly pushdown languages. In *ESA 2016*, volume 57 of *LIPIcs*, pages 43:1–43:17, 2016.

[22] Moses Ganardi, Danny Hucke, Daniel König, Markus Lohrey, and Konstantinos Mamouras. Automata theory on sliding windows. In *STACS 2018*, volume 96 of *LIPIcs*, pages 31:1–31:14, 2018. doi:10.4230/LIPIcs.STACS.2018.31.

[23] Moses Ganardi, Danny Hucke, and Markus Lohrey. Querying regular languages over sliding windows. In *FSTTCS 2016*, volume 65 of *LIPIcs*, pages 18:1–18:14, 2016. doi:10.4230/LIPIcs.FSTTCS.2016.18.

[24] Moses Ganardi, Danny Hucke, and Markus Lohrey. Randomized sliding window algorithms for regular languages. In *ICALP 2018*, volume 107 of *LIPIcs*, pages 127:1–127:13, 2018. doi:10.4230/LIPIcs.ICALP.2018.127.

[25] Moses Ganardi, Danny Hucke, and Markus Lohrey. Sliding window algorithms for regular languages. In *LATA 2018*, volume 10792, pages 26–35, 2018. doi:10.1007/978-3-319-77313-1\_2.

[26] Moses Ganardi, Danny Hucke, Markus Lohrey, and Tatiana Starikovskaya. Sliding window property testing for regular languages. In *ISAAC 2019*, volume 149 of *LIPIcs*, pages 6:1–6:13, 2019. doi:10.4230/LIPIcs.ISAAC.2019.6.

[27] Moses Ganardi, Artur Jeż, and Markus Lohrey. Sliding windows over context-free languages. In *MFCS 2018*, volume 117 of *LIPIcs*, pages 15:1–15:15, 2018. doi:10.4230/LIPIcs.MFCS.2018.15.

[28] Paweł Gawrychowski, Oleg Merkurev, Arseny M. Shur, and Przemysław Uznański. Tight tradeoffs for real-time approximation of longest palindromes in streams. *Algorithmica*, 81(9):3630–3654, 2019. doi:10.1007/s00453-019-00591-8.

[29] Paweł Gawrychowski, Jakub Radoszewski, and Tatiana Starikovskaya. Quasi-periodicity in streams. In *CPM*, volume 128 of *LIPIcs*, pages 22:1–22:14, 2019. doi:10.4230/LIPIcs.CPM.2019.22.
[30] Pawel Gawrychowski and Tatiana Starikovskaya. Streaming dictionary matching with mismatches. In *CPM 2019*, volume 128 of *LIPIcs*, pages 21:1–21:15, 2019. doi:10.4230/LIPIcs.CPM.2019.21.

[31] Pawel Gawrychowski and Przemysław Uznański. Towards unified approximate pattern matching for Hamming and L-1 distance. In *ICALP 2018*, volume 107 of *LIPIcs*, pages 62:1–62:13, 2018. doi:10.4230/LIPIcs.ICALP.2018.62.

[32] Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, and Ely Porat. The streaming k-mismatch problem: Tradeoffs between space and total time. In *CPM 2020*, volume 161 of *LIPIcs*, pages 15:1–15:15, 2020. doi:10.4230/LIPIcs.CPM.2020.15.

[33] Shay Golan, Tsvi Kopelowitz, and Ely Porat. Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams. In *ICALP 2018*, volume 107 of *LIPIcs*, pages 65:1–65:16, 2018. doi:10.4230/LIPIcs.ICALP.2018.65.

[34] Shay Golan and Ely Porat. Real-time streaming multi-pattern search for constant alphabet. In *ESA 2017*, volume 107 of *LIPIcs*, pages 41:1–41:15, 2017. doi:10.4230/LIPIcs.ESA.2017.41.

[35] Tomohiro I. Longest common extensions with recompression. In *CPM 2017*, volume 78 of *LIPIcs*, pages 18:1–18:15, 2017.

[36] Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. *Journal of Computer and System Sciences*, 62(2):367-375, 2001. doi:10.1006/jcss.2000.1727.

[37] Ce Jin, Jelani Nelson, and Kewen Wu. An improved sketching bound for edit distance, 2021. doi:10.4230/LIPIcs.STACS.2021.45.

[38] Richard M. Karp and Michael O. Rabin. Efficient randomized pattern-matching algorithms. *IBM J. of R&D*, 31(2):249-260, 1987.

[39] Dominik Kempa and Tomasz Kociumaka. Resolution of the Burrows-Wheeler transform conjecture, 2020. doi:10.1109/FOCS46700.2020.00097.

[40] S. Kosaraju. Efficient string matching. 1987.

[41] Gad M. Landau, Eugene W. Myers, and Jeanette P. Schmidt. Incremental string comparison. *SIAM J. Comput.*, 27(2):557-582, April 1998.

[42] Gad M. Landau and Uzi Vishkin. Efficient string matching with k mismatches. *Theoretical Computer Science*, 43:239-249, 1986. doi:10.1016/0304-3975(86)90178-7.

[43] Gad M. Landau and Uzi Vishkin. Fast parallel and serial approximate string matching. *J. Algorithms*, 10(2):157-169, 1989. doi:10.1016/0196-6774(89)90010-2.

[44] David Levin and Yuval Peres. *Markov Chains and Mixing Times*. American Mathematical Society, 2017. doi:10.1090/mbk/107.

[45] Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. Recognizing well-parenthesized expressions in the streaming model. *SIAM J. Comput.*, 43(6):1880–1905, 2014. doi:10.1137/130926122.

[46] William J. Masek and Michael S. Paterson. A faster algorithm computing string edit distances. *Journal of Computer and System Sciences*, 20(1):18–31, 1980. doi:https://doi.org/10.1016/0022-0000(80)90002-1.
[47] O. Merkurev and A. M. Shur. Searching runs in streams. In SPIRE 2019, volume 11811 of LNCS, pages 203–220, 2019.

[48] Oleg Merkurev and Arseny M. Shur. Searching long repeats in streams. In CPM 2019, volume 128 of LIPIcs, pages 31:1–31:14, 2019.

[49] Gonzalo Navarro. A guided tour to approximate string matching. ACM Comput. Surv., 33(1):31–88, March 2001. doi:10.1145/375360.375365.

[50] Noam Nisan. Pseudorandom generators for space-bounded computation. Comb., 12(4):449–461, 1992. doi:10.1007/BF01305237.

[51] Takaaki Nishimoto, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Dynamic index and LZ factorization in compressed space. Discrete Applied Mathematics, 274:116–129, 2020. Stringology Algorithms. doi:https://doi.org/10.1016/j.dam.2019.01.014.

[52] Benny Porat and Ely Porat. Exact and approximate pattern matching in the streaming model. In FOCS 2009, pages 315–323, 2009. doi:10.1109/FOCS.2009.11.

[53] Jakub Radoszewski and Tatiana Starikovskaya. Streaming k-mismatch with error correcting and applications. Journal of Information and Computation, 271:104513, 2020. doi:10.1016/j.ic.2019.104513.

[54] Wojciech Rytter. On maximal suffixes and constant-space linear-time versions of KMP algorithm. Theoretical Computer Science, 299(1):763–774, 2003. doi:https://doi.org/10.1016/S0304-3975(02)00590-X.

[55] Süleyman Cenk Sahinalp and Uzi Vishkin. Efficient approximate and dynamic matching of patterns using a labeling paradigm (extended abstract). In FOCS 1996, pages 320–328, 1996. doi:10.1109/SFCS.1996.548491.

[56] Peter H. Sellers. The theory and computation of evolutionary distances: Pattern recognition. Journal of Algorithms, 1(4):359–373, 1980. doi:https://doi.org/10.1016/0196-6774(80)90016-4.

[57] Tatiana Starikovskaya. Communication and streaming complexity of approximate pattern matching. In CPM 2017, volume 78 of LIPIcs, pages 13:1–13:11, 2017. doi:10.4230/LIPIcs.CPM.2017.13.

[58] Alexandre Tiskin. Semi-local string comparison: algorithmic techniques and applications, 2013. arXiv:0707.3619v21.

[59] Esko Ukkonen. Algorithms for approximate string matching. Information and Control, 64(1-3):100–118, 1985. doi:10.1016/S0019-9958(85)80046-2.