We investigate the asymptotic growth of function CS(n), which maps n to the maximum number of distinct squares in a circular word of length n (that is, the maximum number of distinct squares of length at most n in a word ww of length 2n). We improve upon the lower bound of 1.25n established by Amit and Gawrychowski [SPIRE 2017] and the straightforward upper bound of 2n, which follows from the recent result of Brlek and Li [Comb. Theory, 2025] stating that there are fewer than n squares in standard (i.e., non-circular) words of length n. (Previously, Amit and Gawrychowski gave an upper bound of 32/15n using a weaker upper bound on squares in standard words.) Specifically, we show that CS(n) ≤ ⌈1.8 n⌉ and that, for infinitely many n, CS(n) ≥ 1.5n-𝒪(√n). For the lower bound, we exploit the combinatorial structure of Fibonacci words to construct a family of square-rich circular words. For the upper bound, we exploit density properties of the starting positions of long squares, adapting an approach of Amit and Gawrychowski.

We introduce the concept of cyclic covers, which generalizes the classical notion of covers in strings. Given any string X , a factor W of X is called a cyclic cover if each position of X belongs to an occurrence of a cyclic shift of W in X . Two cyclic covers are distinct if one is not a cyclic shift of the other. The cyclic covers problem asks for all distinct cyclic covers of an input string X . We present an algorithm that solves the cyclic covers problem in O ( n log ⁡ n ) time, where n is the length of X . It is based on finding a well-structured set of standard occurrences of a constant number of factors of a cyclic cover candidate W , computing the regions of X covered by cyclic shifts of W , extending those factors, and taking the union of the results. • We introduce the cyclic cover problem. • Two cyclic covers are distinct if one is not a cyclic shift of the other. • The cyclic cover problem requires finding all distinct cyclic covers of X . • We show that for a string of length n, the cyclic cover problem can be solved in O ( n log ⁡ n ) time.

An elastic-degenerate (ED) string $\mathrm{T}$ is a sequence $\mathrm{T} = \mathrm{T}[1] · · · \mathrm{T}[n]$ of $n$ finite sets of strings. The cardinality $m$ of $\mathrm{T}$ is the total number of strings in $\mathrm{T}[i]$, for all $i ∈ [1 . . n]$. The size $\mathrm{N}$ of $\mathrm{T}$ is the total length of all $m$ strings of $\mathrm{T}$. ED strings have been introduced to represent a set of closely-related DNA sequences. Let $P = P[1 . . p]$ be a pattern of length $p$ and $k > 0$ be an integer. We consider the problem of $k$-Approximate ED String Matching (EDSM): searching $k$-approximate occurrences of $P$ in the language of $\mathrm{T}$. We call $k$-Approximate EDSM under the Hamming distance, $k$-Mismatch EDSM; and we call $k$-Approximate EDSM under edit distance, $k$-Edit EDSM. Bernardini et al. (Theoretical Computer Science, 2020) showed a simple $\mathcal{O}(kmp + kN)$-time algorithm for $k$-Mismatch EDSM and an $\mathcal{O}(k2mp + kN)$-time algorithm for $k$-Edit EDSM. We improve the dependency on $k$ in both results, obtaining an $\mathcal{Õ}(k2/3mp +√kN)$-time algorithm for $k$-Mismatch EDSM and an $\mathcal{Õ}(kmp + kN)$-time algorithm for $k$-Edit EDSM. Bernardini et al. (Theory of Computing Systems, 2024) presented several algorithms for 1-Approximate EDSM working in $\mathcal{Õ}(np2 + N)$ time. They have also left the possibility to generalize these solutions for $k > 1$ as an open problem. We improve the runtime of their solution for 1-Mismatch and 1-Edit EDSM from $\mathcal{Õ}(np2 + N)$ to $\mathcal{O}(np2 + N)$. We further show algorithms for $k$-Approximate EDSM for the Hamming and edit distances working in $\mathcal{Õ}(np2 + N)$ time, for any constant $k > 0$. Finally, we show how our techniques can be applied to improve upon the complexity of the $k$-Approximate ED String Intersection and $k$-Approximate Doubly EDSM problems that were introduced very recently by Gabory et al. (Information and Computation, 2025).

Computing shortest directed paths in de Bruijn graphs is well studied and well understood. This is not the case for computing undirected paths, which is much more challenging algorithmically. In this paper, we present a general framework for computing shortest undirected paths in arbitrary de Bruijn graphs, that is, arbitrary subgraphs of the complete de Bruijn graph. We then present an application of our techniques for making any arbitrary order-k de Bruijn graph G(V,E) weakly connected by adding a set of edges of minimum total cost. This improves the running time of the recent (2-2/d)-approximation algorithm by Bernardini et al. [CPM 2024] from 𝒪(k|V|²) to 𝒪(k|V|log d) time, where d is the number of weakly connected components of graph G.

An elastic-degenerate (ED) string T is a sequence of n sets T [ 1 ] , … , T [ n ] containing m strings in total whose cumulative length is N . We call n , m , and N the length, the cardinality and the size of T , respectively. The language of T is defined as L ( T ) = { S 1 ⋯ S n : S i ∈ T [ i ] for all i ∈ [ 1 , n ] } . Given two ED strings, how fast can we check whether the two languages they represent have a nonempty intersection? We call this problem the ED String Intersection (EDSI) problem. For two ED strings T 1 and T 2 of lengths n 1 and n 2 , cardinalities m 1 and m 2 , and sizes N 1 and N 2 , respectively, we show the following: • There is no O ( ( N 1 N 2 ) 1 − ϵ ) -time algorithm, for any ϵ > 0 , for EDSI even if T 1 and T 2 are over a binary alphabet, unless the Strong Exponential-Time Hypothesis is false. • There is no combinatorial O ( ( N 1 + N 2 ) 1.2 − ϵ f ( n 1 , n 2 ) ) -time algorithm, for any ϵ > 0 and any function f , for EDSI even if T 1 and T 2 are over a binary alphabet, unless the Boolean Matrix Multiplication conjecture is false. • An O ( N 1 log ⁡ N 1 log ⁡ n 1 + N 2 log ⁡ N 2 log ⁡ n 2 ) -time algorithm for outputting a compact representation of the intersection language of two unary ED strings. When T 1 and T 2 are given in a compact representation, we show that the problem is NP-complete. • An O ( N 1 m 2 + N 2 m 1 ) -time algorithm for EDSI. • An O ˜ ( N 1 ω − 1 n 2 + N 2 ω − 1 n 1 ) -time algorithm for EDSI, where ω is the matrix multiplication exponent; the O ˜ notation suppresses factors that are polylogarithmic in the input size.

We introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word C is an s-cover of a word S if the occurrences of C in S as subsequences cover all the positions in S . The s-covers seem to be computationally much harder than standard covers of words (cf. Apostolico et al. (1991) [1] ), but, on the other hand, much easier than the related shuffle powers (Warmuth and Haussler (1984) [6] ). We give a linear-time algorithm for testing if a candidate word C is an s-cover of a word S over a polynomially-bounded integer alphabet. We also give an algorithm for finding a shortest s-cover of a word S , which in the case of a constant-sized alphabet, also runs in linear time. The words without proper s-cover are called s-primitive. We complement our algorithmic results with explicit lower and an upper bound on the length of a longest s-primitive word. Both bounds are exponential in the size of the alphabet. The upper bound presented here improves the bound given in the conference version of this paper [SPIRE 2022].

Strings in the real world are often encoded with some level of uncertainty, for example, due to: unreliable data measurements; flexible sequence modeling; or noise introduced for privacy protection. In the character-level uncertainty model, an uncertain string X of length$n$on an alphabetΣ is a sequence of$n$probability distributions over Σ. Given an uncertain string$X$and a weight threshold$\frac {1}{z}\in(0,1)$, we say that pattern$P$occurs in$X$at position$i$, if the product of probabilities of the letters of$P$at positions$i,\ldots, i+ \vert P\vert-1$is at least$\frac {1}{z}$. While indexing standard strings for online pattern searches can be performed in linear time and space, indexing uncertain strings is much more challenging. Specifically, the state-of-the-art index for uncertain strings has$O(nz)$size, requires$O(nz)$time and$O(nz)$space to be constructed, and answers pattern matching queries in the optimal$O(m+ [Occl)$time, where$m$is the length of$P$and$\vert Occ\vert$is the total number of occurrences of$P$in$X$. For large$n$and (moderate)$z$values, this index is completely impractical to construct, which outweighs the benefit of the supported optimal pattern matching queries. We were thus motivated to design a space-efficient index at the expense of slower yet competitive pattern matching queries. We show that when we have at hand a lower bound ℓ on the length of the supported pattern queries, as is often the case in real-world applications, we can slash the index size and the construction space roughly by ℓ. In particular, we propose an index of$Q (n/ \log z)$expected size, which can be constructed using$Q (n/ \log z)$expected space, and supports very fast pattern matching queries in expectation, for patterns of length m ≥ ℓ. We have implemented and evaluated several versions of our index. The best-performing version of our index is up to two orders of magnitude smaller than the state of the art in terms of both index size and construction space, while offering faster or very competitive query and construction times.

Time series are ubiquitous in domains ranging from medicine to marketing and finance. Frequent Pattern Mining (FPM) from a time series has thus received much attention. This general problem has been studied under different matching relations determining whether two time series match or not. Recently, it has been studied under the order-preserving (OP) matching relation stating that a match occurs when two time series have the same relative order (i.e., ranks) on their elements. Thus, a frequent OP pattern captures a trend shared by sufficiently many parts of the input time series. Here, we propose exact, highly scalable algorithms for FPM in the OP setting. Our algorithms employ an OP suffix tree (OPST) as an index to store and query time series efficiently. Unfortunately, there are no practical algorithms for OPST construction. Thus, we first propose a novel and practical$\mathcal{O}(n\sigma\log\sigma)$-time and$\mathcal{O}(n)$- space algorithm for constructing the OPST of a length-n time series over an alphabet of size$\sigma$. We also propose an alternative faster OPST construction algorithm running in$\mathcal{O}(n\log\sigma)$time using$\mathcal{O}(n)$space; this algorithm is mainly of theoretical interest. Then, we propose an exact$\mathcal{O}(n)$-time and$\mathcal{O}(n)$-space algorithm for mining all maximal frequent OP patterns, given an OPST. This significantly improves on the state of the art, which takes$\Omega(n^{3})$time in the worst case. We also formalize the notion of closed frequent OP patterns and propose an exact$\mathcal{O}(n)$-time and$\mathcal{O}(n)$-space algorithm for mining all closed frequent OP patterns, given an OPST. We conducted experiments using real-world, multi-million letter time series showing that our$\mathcal{O}(n\sigma\log\sigma)$- time OPST construction algorithm runs in$\mathcal{O}(n)$time on these datasets despite the$\mathcal{O}(n\sigma\log\sigma)$bound; that our frequent pattern mining algorithms are up to orders of magnitude faster than the state of the art and natural Apriori-like baselines; and that OP pattern-based clustering is effective.

In the $k$-Edit Circular Pattern Matching ($k$-Edit CPM) problem, we are given a length-$n$ text $T$, a length-$m$ pattern $P$, and a positive integer threshold $k$, and we are to report all starting positions of the substrings of $T$ that are at edit distance at most $k$ from some cyclic rotation of $P$. In the decision version of the problem, we are to check if any such substring exists. Very recently, Charalampopoulos et al. [ESA 2022] presented $O(nk^2)$-time and $O(nk \log^3 k)$-time solutions for the reporting and decision versions of $k$-Edit CPM, respectively. Here, we show that the reporting and decision versions of $k$-Edit CPM can be solved in $O(n+(n/m) k^6)$ time and $O(n+(n/m) k^5 \log^3 k)$ time, respectively, thus obtaining the first algorithms with a complexity of the type $O(n+(n/m) \mathrm{poly}(k))$ for this problem. Notably, our algorithms run in $O(n)$ time when $m=Ω(k^6)$ and are superior to the previous respective solutions when $m=ω(k^4)$. We provide a meta-algorithm that yields efficient algorithms in several other interesting settings, such as when the strings are given in a compressed form (as straight-line programs), when the strings are dynamic, or when we have a quantum computer. We obtain our solutions by exploiting the structure of approximate circular occurrences of $P$ in $T$, when $T$ is relatively short w.r.t. $P$. Roughly speaking, either the starting positions of approximate occurrences of rotations of $P$ form $O(k^4)$ intervals that can be computed efficiently, or some rotation of $P$ is almost periodic (is at a small edit distance from a string with small period). Dealing with the almost periodic case is the most technically demanding part of this work; we tackle it using properties of locked fragments (originating from [Cole and Hariharan, SICOMP 2002]).

Abstract An elastic-degenerate (ED) string is a sequence of n finite sets of strings of total length N, introduced to represent a set of related DNA sequences, also known as a pangenome. The ED string matching (EDSM) problem consists in reporting all occurrences of a pattern of length m in an ED text. The EDSM problem has recently received some attention by the combinatorial pattern matching community, culminating in an $$\mathcal {\tilde{O}}(nm^{\omega -1})+\mathcal {O}(N)$$ O ~ ( n m ω - 1 ) + O ( N ) -time algorithm [Bernardini et al., SIAM J. Comput. 2022], where $$\omega $$ ω denotes the matrix multiplication exponent and the $$\mathcal {\tilde{O}}(\cdot )$$ O ~ ( · ) notation suppresses polylog factors. In the k-EDSM problem, the approximate version of EDSM, we are asked to report all pattern occurrences with at most k errors. k-EDSM can be solved in $$\mathcal {O}(k^2mG+kN)$$ O ( k 2 m G + k N ) time, under edit distance, or $$\mathcal {O}(kmG+kN)$$ O ( k m G + k N ) time, under Hamming distance, where G denotes the total number of strings in the ED text [Bernardini et al., Theor. Comput. Sci. 2020]. Unfortunately, G is only bounded by N, and so even for $$k=1$$ k = 1 , the existing algorithms run in $$\varOmega (mN)$$ Ω ( m N ) time in the worst case. In this paper we make progress in this direction. We show that 1-EDSM can be solved in $$\mathcal {O}((nm^2 + N)\log m)$$ O ( ( n m 2 + N ) log m ) or $$\mathcal {O}(nm^3 + N)$$ O ( n m 3 + N ) time under edit distance. For the decision version of the problem, we present a faster $$\mathcal {O}(nm^2\sqrt{\log m} + N\log \log m)$$ O ( n m 2 log m + N log log m ) -time algorithm. We also show that 1-EDSM can be solved in $$\mathcal {O}(nm^2 + N\log m)$$ O ( n m 2 + N log m ) time under Hamming distance. 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 rely on employing and adapting the k-errata trees for indexing with errors [Cole et al., STOC 2004]. This is an extended version of a paper presented at LATIN 2022.

An elastic-degenerate (ED) string T is a sequence of n sets T[1],…,T[n] containing m strings in total whose cumulative length is N. We call n, m, and N the length, the cardinality and the size of T, respectively. The language of T is defined as ℒ(T) = {S_1 ⋯ S_n : S_i ∈ T[i] for all i ∈ [1,n]}. ED strings have been introduced to represent a set of closely-related DNA sequences, also known as a pangenome. The basic question we investigate here is: Given two ED strings, how fast can we check whether the two languages they represent have a nonempty intersection? We call the underlying problem the ED String Intersection (EDSI) problem. For two ED strings T₁ and T₂ of lengths n₁ and n₂, cardinalities m₁ and m₂, and sizes N₁ and N₂, respectively, we show the following: - There is no 𝒪((N₁N₂)^{1-ε})-time algorithm, thus no 𝒪((N₁m₂+N₂m₁)^{1-ε})-time algorithm and no 𝒪((N₁n₂+N₂n₁)^{1-ε})-time algorithm, for any constant ε > 0, for EDSI even when T₁ and T₂ are over a binary alphabet, unless the Strong Exponential-Time Hypothesis is false. - There is no combinatorial 𝒪((N₁+N₂)^{1.2-ε}f(n₁,n₂))-time algorithm, for any constant ε > 0 and any function f, for EDSI even when T₁ and T₂ are over a binary alphabet, unless the Boolean Matrix Multiplication conjecture is false. - An 𝒪(N₁log N₁log n₁+N₂log N₂log n₂)-time algorithm for outputting a compact (RLE) representation of the intersection language of two unary ED strings. In the case when T₁ and T₂ are given in a compact representation, we show that the problem is NP-complete. - An 𝒪(N₁m₂+N₂m₁)-time algorithm for EDSI. - An Õ(N₁^{ω-1}n₂+N₂^{ω-1}n₁)-time algorithm for EDSI, where ω is the exponent of matrix multiplication; the Õ notation suppresses factors that are polylogarithmic in the input size. We also show that the techniques we develop have applications outside of ED string comparison.

In the all-pairs suffix-prefix (APSP) problem, we are given a dictionary R of k strings, S_1,…,S_k, of total length n, and we are asked to find the length SPL_{i,j} of the longest string that is both a suffix of S_i and a prefix of S_j, for all i,j ∈ [1,k]. APSP is a classic problem in string algorithms with many applications in bioinformatics. When all strings of the dictionary are over an integer alphabet of size σ ≤ n^𝒪(1), APSP can be solved in the optimal 𝒪(n+k²) time with the use of the generalized suffix tree of the dictionary [Gusfield et al., Inf. Process. Lett. 1992]. In many bioinformatics applications, such as in sequence assembly, the size k of dictionary R is very large. In particular, k² usually dominates n, and thus the k² factor is the bottleneck both in the time and in the space complexity of such applications. We thus initiate a holistic study on several data structure variants of APSP. In particular, we consider the following types of queries: - One-to-One(i,j): output SPL_{i,j}. - One-to-All(i): output SPL_{i,j} for every j ∈ [1,k]. - Report(i,𝓁): output all distinct j ∈ [1,k] such that SPL_{i,j} ≥ 𝓁, where 𝓁 ≥ 0 is an integer. - Count(i,𝓁): output the number of distinct j ∈ [1,k] such that SPL_{i,j} ≥ 𝓁, where 𝓁 ≥ 0 is an integer. - Top(i,K): output K distinct j ∈ [1,k] with the highest values of SPL_{i,j} breaking ties arbitrarily. We assume the standard word RAM model of computation with word size w = Ω(log n) and an integer alphabet of size σ ≤ n^𝒪(1). We show the following upper bounds: Query | Space (words) | Query time | Note One-to-One(i,j) | 𝒪(n) | 𝒪(log log k) | Theorem 11 One-to-All(i) | 𝒪(n) | 𝒪(k) | Theorem 14 Report(i,𝓁) | 𝒪(n) | 𝒪(log n/log log n+output) | Theorem 19(i) Count(i,𝓁) | 𝒪(n) | 𝒪(log n/log log n) | Theorem 19(ii) Top(i,K) | 𝒪(n) | 𝒪(log² n/log log n+K) | Theorem 22 We also present efficient algorithms for constructing these data structures.

We consider approximate circular pattern matching (CPM, in short) under the Hamming and edit distance, in which we are given a length-$n$ text $T$, a length-$m$ pattern $P$, and a threshold $k>0$, and we are to report all starting positions of fragments of $T$ (called occurrences) that are at distance at most $k$ from some cyclic rotation of $P$. In the decision version of the problem, we are to check if any such occurrence exists. All previous results for approximate CPM were either average-case upper bounds or heuristics, except for the work of Charalampopoulos et al. [CKP$^+$, JCSS'21], who considered only the Hamming distance. For the reporting version of the approximate CPM problem, under the Hamming distance we improve upon the main algorithm of [CKP$^+$, JCSS'21] from ${\cal O}(n+(n/m)\cdot k^4)$ to ${\cal O}(n+(n/m)\cdot k^3)$ time; for the edit distance, we give an ${\cal O}(nk^2)$-time algorithm. We also consider the decision version of the approximate CPM problem. Under the Hamming distance, we obtain an ${\cal O}(n+(n/m)\cdot k^2\log k/\log\log k)$-time algorithm, which nearly matches the algorithm by Chan et al. [CGKKP, STOC'20] for the standard counterpart of the problem. Under the edit distance, the ${\cal O}(nk\log^2 k)$ running time of our algorithm nearly matches the ${\cal O}(nk)$ running time of the Landau-Vishkin algorithm [LV, J. Algorithms'89]. As a stepping stone, we propose an ${\cal O}(nk\log^2 k)$-time algorithm for the Longest Prefix $k'$-Approximate Match problem, proposed by Landau et al. [LMS, SICOMP'98], for all $k'\in \{1,\dots,k\}$. We give a conditional lower bound that suggests a polynomial separation between approximate CPM under the Hamming distance over the binary alphabet and its non-circular counterpart. We also show that a strongly subquadratic-time algorithm for the decision version of approximate CPM under edit distance would refute SETH.

We consider two notions of covers of a two-dimensional string T. A (rectangular) subarray P of T is a 2D-cover of T if each position of T is in an occurrence of P in T. A one-dimensional string S is a 1D-cover of T if its vertical and horizontal occurrences in T cover all positions of T. We show how to compute the smallest-area 2D-cover of an m × n array T in the optimal 𝒪(N) time, where N = mn, all aperiodic 2D-covers of T in 𝒪(N log N) time, and all 2D-covers of T in N^{4/3}⋅ log^{𝒪(1)}N time. Further, we show how to compute all 1D-covers in the optimal 𝒪(N) time. Along the way, we show that the Klee’s measure of a set of rectangles, each of width and height at least √n, on an n × n grid can be maintained in √n⋅ log^{𝒪(1)}n time per insertion or deletion of a rectangle, a result which could be of independent interest.

We prove 3SUM-hardness (no strongly subquadratic-time algorithm, assuming the 3SUM conjecture) of several problems related to finding Abelian square and additive square factors in a string. In particular, we conclude conditional optimality of the state-of-the-art algorithms for finding such factors. Overall, we show 3SUM-hardness of (a) detecting an Abelian square factor of an odd half-length, (b) computing centers of all Abelian square factors, (c) detecting an additive square factor in a length-$n$ string of integers of magnitude $n^{\mathcal{O}(1)}$, and (d) a problem of computing a double 3-term arithmetic progression (i.e., finding indices $i \ne j$ such that $(x_i+x_j)/2=x_{(i+j)/2}$) in a sequence of integers $x_1,\dots,x_n$ of magnitude $n^{\mathcal{O}(1)}$. Problem (d) is essentially a convolution version of the AVERAGE problem that was proposed in a manuscript of Erickson. We obtain a conditional lower bound for it with the aid of techniques recently developed by Dudek et al. [STOC 2020]. Problem (d) immediately reduces to problem (c) and is a step in reductions to problems (a) and (b). In conditional lower bounds for problems (a) and (b) we apply an encoding of Amir et al. [ICALP 2014] and extend it using several string gadgets that include arbitrarily long Abelian-square-free strings. Our reductions also imply conditional lower bounds for detecting Abelian squares in strings over a constant-sized alphabet. We also show a subquadratic upper bound in this case, applying a result of Chan and Lewenstein [STOC 2015].

We consider the problem of preprocessing a text T of length n and a dictionary 𝒟 in order to be able to efficiently answer queries CountDistinct(i,j), that is, given i and j return the number of patterns from 𝒟 that occur in the fragment T[i..j]. The dictionary is internal in the sense that each pattern in 𝒟 is given as a fragment of T. This way, the dictionary takes space proportional to the number of patterns d=|𝒟| rather than their total length, which could be Θ(n⋅ d). An 𝒪̃(n+d)-size data structure that answers CountDistinct(i,j) queries 𝒪(log n)-approximately in 𝒪̃(1) time was recently proposed in a work that introduced internal dictionary matching [ISAAC 2019]. Here we present an 𝒪̃(n+d)-size data structure that answers CountDistinct(i,j) queries 2-approximately in 𝒪̃(1) time. Using range queries, for any m, we give an 𝒪̃(min(nd/m,n²/m²)+d)-size data structure that answers CountDistinct(i,j) queries exactly in 𝒪̃(m) time. We also consider the special case when the dictionary consists of all square factors of the string. We design an 𝒪(n log² n)-size data structure that allows us to count distinct squares in a text fragment T[i..j] in 𝒪(log n) time.

The notions of periodicity and repetitions in strings, and hence these of runs and squares, naturally extend to two-dimensional strings. We consider two types of repetitions in 2D-strings: 2D-runs and quartics (quartics are a 2D-version of squares in standard strings). Amir et al. introduced 2D-runs, showed that there are 𝒪(n³) of them in an n × n 2D-string and presented a simple construction giving a lower bound of Ω(n²) for their number (Theoretical Computer Science, 2020). We make a significant step towards closing the gap between these bounds by showing that the number of 2D-runs in an n × n 2D-string is 𝒪(n² log² n). In particular, our bound implies that the 𝒪(n²log n + output) run-time of the algorithm of Amir et al. for computing 2D-runs is also 𝒪(n² log² n). We expect this result to allow for exploiting 2D-runs algorithmically in the area of 2D pattern matching. A quartic is a 2D-string composed of 2 × 2 identical blocks (2D-strings) that was introduced by Apostolico and Brimkov (Theoretical Computer Science, 2000), where by quartics they meant only primitively rooted quartics, i.e. built of a primitive block. Here our notion of quartics is more general and analogous to that of squares in 1D-strings. Apostolico and Brimkov showed that there are 𝒪(n² log² n) occurrences of primitively rooted quartics in an n × n 2D-string and that this bound is attainable. Consequently the number of distinct primitively rooted quartics is 𝒪(n² log² n). The straightforward bound for the maximal number of distinct general quartics is 𝒪(n⁴). Here, we prove that the number of distinct general quartics is also 𝒪(n² log² n). This extends the rich combinatorial study of the number of distinct squares in a 1D-string, that was initiated by Fraenkel and Simpson (Journal of Combinatorial Theory, Series A, 1998), to two dimensions. Finally, we show some algorithmic applications of 2D-runs. Specifically, we present algorithms for computing all occurrences of primitively rooted quartics and counting all general distinct quartics in 𝒪(n² log² n) time, which is quasi-linear with respect to the size of the input. The former algorithm is optimal due to the lower bound of Apostolico and Brimkov. The latter can be seen as a continuation of works on enumeration of distinct squares in 1D-strings using runs (Crochemore et al., Theoretical Computer Science, 2014). However, the methods used in 2D are different because of different properties of 2D-runs and quartics.

We introduce the Longest Common Circular Factor (LCCF) problem in which, given strings $S$ and $T$ of length $n$, we are to compute the longest factor of $S$ whose cyclic shift occurs as a factor of $T$. It is a new similarity measure, an extension of the classic Longest Common Factor. We show how to solve the LCCF problem in $O(n \log^5 n)$ time.

The k -mismatch problem consists in computing the Hamming distance between a pattern P of length m and every length- m substring of a text T of length n , if this distance is no more than k . In many real-world applications, any cyclic shift of P is a relevant pattern, and thus one is interested in computing the minimal distance of every length- m substring of T and any cyclic shift of P . This is the circular pattern matching with k mismatches ( k -CPM) problem. A multitude of papers have been devoted to solving this problem but, to the best of our knowledge, only average-case upper bounds are known. In this paper, we present the first non-trivial worst-case upper bounds for the k -CPM problem. Specifically, we show an \(\mathcal {O}(nk)\) -time algorithm and an \(\mathcal {O}(n+\frac{n}{m}\,{\small k^5})\) -time algorithm. The latter algorithm applies in an extended way a technique that was very recently developed for the k -mismatch problem [Bringmann et al., SODA 2019].