1 Introduction↩︎

The pattern matching, as well as the dictionary matching problems, have been extensively studied for decades, where we need to preprocess a dictionary \(\mathcal{D}\) containing one or multiple patterns to answer their occurrences in each query text. In addition to classical methods [1], [2], there are also studies on developing approximate algorithms [3]–[6], and algorithms in the dynamic dictionary setting [7]–[11].

In this paper, we consider the internal setting where each pattern or query is represented by a substring of a given large text \(T\). Such an “internal” concept is not new in string algorithms. For example, the famous suffix array algorithm [12]–[15] sorts all suffixes of \(T\), which helps to answer multiple types of queries such as the longest common prefix (LCP) of two suffixes. In this case, all related texts (suffixes) are internal with respect to \(T\). Computing the LCP of any two suffixes can be easily generalized to computing the LCP of any two substrings (fragments), known as the longest common extension (LCE) queries introduced by Landau and Vishkin [16], which could be one of the earliest internal queries.

In recent years, the internal pattern matching (IPM) problem has been widely studied, which requires us to compute the occurrences of a substring of \(T\) in another substring of \(T\). Recent research has developed algorithms that run in sublogarithmic time and occupy near-linear space [17]–[19]. Benefit from the IPM algorithms, many internal queries have been studied, such as shortest unique substrings [20], shortest absent string [21], BWT substring compression [22], circular pattern matching [23], etc. Moreover, the IPM queries have been used in some other problems, including approximate pattern matching [24], [25], approximate circular pattern matching [26], [27], RNA folding [28], and computing string covers [29].

Similar to dictionary matching, a natural generalization of the IPM problem is the newly proposed internal dictionary matching (IDM) problem, where we consider multiple patterns. It was first introduced and studied by Charalampopoulos et al. [30], [31]. In such a setting, given a large text \(T\) of length \(n\) in advance, we consider a dictionary \(\mathcal{D}\) consisting of substrings of \(T\). We denote the number of patterns as \(d\). The following types of internal queries are studied in the IDM problem:

• \(\mathrm{\small Exists}(l,r)\): Decide whether at least one pattern from \(\mathcal{D}\) occurs in \(T[l,r]\).

• \(\mathrm{\small Report}(l,r)\): Report all occurrences of all patterns from \(\mathcal{D}\) in \(T[l,r]\).

• \(\mathrm{\small ReportDistinct}(l,r)\): Report all distinct patterns from \(\mathcal{D}\) in \(T[l,r]\).

• \(\mathrm{\small Count}(l,r)\): Count the number of all occurrences of all patterns from \(\mathcal{D}\) in \(T[l,r]\).

• \(\mathrm{\small CountDistinct}(l,r)\): Count the number of distinct patterns from \(\mathcal{D}\) in \(T[l,r]\).

Compared to the classical dictionary matching problem, the IDM problem is especially applicable to any internal dictionary whose total length of all patterns (substrings) \(L\) is much larger than the number of patterns \(d\), such as the dictionary of all palindrome substrings, all square substrings, and all non-primitive substrings. Combined with algorithms that efficiently extract the endpoints of patterns [32]–[34], an IDM algorithm can answer queries regarding such an internal dictionary in time and space not depending on \(L.\) IDM algorithms for the palindromes case [35] and the squares case [31] have already been developed. Same as IPM, IDM also has many practical applications. For example, in bioinformatics, the multi-pattern matching query has many deployed applications, most of which are under the internal setting and can be reduced to IDM [36], [37].

Previous work [30] shows that the product of the time to process an update to \(\mathcal{D}\) and the time to answer an internal query cannot be \(O(n^{1-\epsilon})\) for any constant \(\epsilon>0\), unless the Online Boolean Matrix-Vector Multiplication conjecture [38] is false. This conditional lower bound demonstrates the hardness of efficient algorithms in the dynamic dictionary case. In this paper, we focus mainly on the case of a static dictionary.

1.1 Our Results↩︎

In this paper, we propose a new \(O(n)\)-sized data structure named Basic Substring Structure (BASS) that organizes \(T\)’s substrings in a novel way (3). BASS builds upon the idea of equivalence classes of substrings, an approach that has been explored in previous work, such as the seminal work by Blumer et al. [39], [40], which introduced the concept of equivalence classes in the context of the compact acyclic word graph (CDAWG). While the equivalence class concept is indeed not new, the key contribution of this paper lies in the grid structure that organizes these equivalence classes in a two-dimensional grid. This novel structure enables the efficient handling of substring queries, something that earlier works did not fully address. In contrast to traditional representations like the CDAWG, which represent equivalence classes in a graph-like structure, the grid-based approach in BASS allows for more efficient indexing and querying of patterns.

BASS is the first data structure that is able to handle all types of queries of the IDM problem in nearly optimal query and preprocessing time. This contrasts with previous works where they treated different queries with tailored approaches. 1 gives an overview of our BASS-based algorithms on different query types compared to previous results. All algorithms take \(\tilde{O}(n+d)\)² space.

1.1.1 Counting Distinct Patterns↩︎

By introducing an extra parameter \(m\), the previous best result answers CountDistinct queries in \(\tilde{O}(m)\) time after \(\tilde{O}(n^2/m+d)\) or \(\tilde{O}(nd/m+d)\) preprocessing [31]. The question of whether any data structure answers CountDistinct queries exactly in \(\tilde{O}(1)\) time each after \(\tilde{O}(n+d)\) preprocessing was open. As one of the main contributions, we answer this question affirmatively:

Similar to [30], for the case of a dynamic dictionary, where patterns can be added or deleted, we can construct algorithms that process updates in \(\tilde{O}(n^\alpha)\) time and answer queries CountDistinct\((l,r)\) in \(\tilde{O}(n^{1-\alpha})\) time for any \(0<\alpha<1\). For this type of query, this is the first result that matches the known conditional lower bound up to subpolynomial factors.

1.1.2 Other Internal Queries↩︎

As in previous work [30], Exists, Report, ReportDistinct, Count can be answered in \(\tilde{O}(1+|\text{output}|)\) time after \(\tilde{O}(n+d)\) preprocessing of \(T\). Our BASS-based algorithms match all previous results and achieve some improvements.

For the Count query, previous works take \(O(\frac{\log^2 n}{\log\log n})\) per query after \(O(\frac{n\log n}{\log \log n}+d\log^{3/2} n)\) preprocessing. Our result improves the run time for both query and preprocessing:

Also, we prove that there is an unconditional lower bound on Count\((l,r)\), stating that \(O(\frac{\log n}{\log \log n})\) query time is optimal for all data structures of size \(\tilde{O}(n)\) [41]. Thus, our query time for \(\mathrm{\small Count}(l,r)\) queries is optimal.

For ReportDistinct queries that output all distinct patterns that occurred, using the same preprocessing time, our query time improves to \(O(1+|\text{output}|)\) from \(O(\log n +|\text{output}|)\):

For Exists, Report queries, although taking different approaches, both our algorithm and previous works need \(O(n+d)\) preprocessing time and \(O(1+|\text{output}|)\) query time ([theo:exist], [theo:report]). In addition, BASS can find further applications, particularly for various kinds of internal queries. We discuss the range longest common substring (RLCS) problem as a showcase. Specifically, given two strings \(S\) and \(T\), each query LCS\((l,r)\) requires computing the longest common substring between \(S\) and \(T[l,r]\). With BASS, we can construct a data structure with \(O(n)\) preprocessing time and constant query time, achieving optimality ([theo:rlcs]) and improving the previous best result of \(O(\log n)\) query time [42].

2 Preliminaries↩︎

We first give some common definitions and notations for strings, aligned with [43]. Let \(T=T_1T_2T_3\cdots T_n\) be a string of length \(|T|=n\) over a linearly sortable alphabet \(\Sigma\). We refer to elements in \(\Sigma\) as letters or characters. For any two indexes \(1 \leq l \leq r \leq n\), the string constructed by concatenating \(T_l,T_{l+1},\cdots,T_r\) is denoted as \(T[l,r]\).

2.0.0.1 Substrings, prefixes, and suffixes.

For two strings \(T\) and \(t\), \(t\) is a substring of \(T\) if and only if there exist some indexes \(1 \leq l \leq r \leq |T|\) such that \(T[l,r]=t\). We can also say that \(t\) occurs in \(T\) or \(T\) contains \(t\). A prefix of \(T\) is a substring of the form \(T[1, i]\) for some \(1 \leq i \leq |T|\). Similarly, a suffix of \(T\) is a substring of the form \(T[i, |T|]\).

2.0.0.2 Occurrence sets.

Given a string \(T\), for any pattern \(t\), \(\mathtt{occ}_{T}(t)\) is defined as the set of distinct index pairs \((l,r)\) \((1 \leq l \leq r \leq n)\) such that \(T[l,r]=t\), indicating the occurrences of \(t\) in \(T\). If the dictionary string is not ambiguous, we can also write \(\mathtt{occ}(t)\).

A trie is a tree data structure where each edge is labeled by a single character, with paths from the root to specific nodes forming complete words. For a set \(S\) of strings, we denote the trie built by \(S\) as \(\mathcal{E}(S)\). Also, we denote \(\texttt{str}'(u)\) as the string formed by the path from the root to \(u\). If \(\texttt{str}'(u)\in S\), we call \(u\) a terminal node.

For a string \(T\) over a linearly sortable alphabet \(\Sigma\), the suffix tree \(\mathcal{T}(T)\) is a compact trie built by all suffixes of \(T\). If a node in trie has only one child and is not a terminal node, the node is compressed. Thus, edges are labeled with character sequences instead of a single character. We denote \(\texttt{str(u)}\) as the set of substrings \(\texttt{str}'(v)\) for all \(v\) that is compressed into \(u\). Thus, the union of all \(\texttt{str}(u)\) is all different substrings of \(T\), and we say a node \(u\) recognizes a substring \(t\) if \(t\in \texttt{str}(u)\). Also, it is proved that substrings in \(\texttt{str}(u)\) have the same set of start positions. Additionally, for non-root node \(u\), we denote \(\texttt{parent}(u)\) to be the parent of \(u\), and by definition, any string in \(\texttt{str}(\texttt{parent}(u))\) is a prefix of all strings in \(\texttt{str}(u)\). Lastly, we denote \(\texttt{maxstr}(u)\) as longest string stored in \(\texttt{str}(u)\) and \(\texttt{len}(u)\) as the length of \(\texttt{maxstr}(u)\).

3 Basic Substring Structure↩︎

3.1 Grid↩︎

The Basic Substring Structure (BASS) of a string \(T\), denoted by \(\mathtt{BASS}(T)\), is based on a two-dimensional grid \(G\) which maps every substring \(T[l, r]\) to a point \((l, r)\). Each row \(i\) corresponds to all the substrings of \(T\) ending at position \(i\), and each column \(j\) corresponds to all the substrings of \(T\) starting at position \(j\). 2 (a) gives an example with \(T=\texttt{abbab}\).

Recall that \(\mathrm{\small Count}(l,r)\) computes the number of all occurrences of all patterns in \(T[l,r]\). For every substring \(T[l,r]\), we mark its corresponding point \((l,r)\) if and only if \(T[l,r] \in \mathcal{D}\). The answer to \(\mathrm{\small Count}(l,r)\) is equivalent to the number of marked points within the rectangle \([l, \infty] \times [-\infty, r]\). However, since there could be up to \(O(nd)\) marked points, it is inefficient to preprocess them one by one.

3.2 Equivalence Class↩︎

Now, we show how these points can be efficiently stored. To do this, we need to introduce the concept of equivalence classes in the BASS. We begin by defining an extension operation for any substring \(t\):

The extension operation is well defined because, for any substring \(t\), there is only one longest such string \(s\). The proof of this uniqueness can be found in 6.

For any two substrings \(t_1\) and \(t_2\) of \(T\), we define them as equivalent if and only if \(\mathtt{ext}(t_1)=\mathtt{ext}(t_2)\). That is to say, substrings \(s\) that share the same value of \(\mathtt{ext}(s)\) are classified into the same equivalence class.

Now, we will map the equivalence classes to the grid \(G\). To illustrate, we assign a unique color to each equivalence class \(C\) and color each cell \((i, j)\) as the color of the equivalence class of \(T[i, j]\). Then, we call each maximal connected component with a single color in the grid as a block, which exhibits a staircase-like shape as shown in 2 (b). More formally, we have the following lemma.

Taking the block colored in red in 2 (b) as an example, we have \(\texttt{left}_{B}=1\), \(\texttt{right}_{B}=3\) and \(\texttt{top}_{B}=5\). For each column \(i \in [1,3]\), we have \(b_1=3,b_2=3,b_3=4\). These parameters precisely describe the shape and position of the block. Furthermore, as shown in 2, all blocks from the same equivalence class have the same shape. Therefore, we only preprocess one corresponding block for each equivalence class.

3.3 Relationships between Blocks↩︎

There are further relationships between neighboring blocks. Here, we denote two blocks as neighbors if they share a common edge on any row or column in the grid. If we treat each equivalence class as a node and establish edges between neighboring classes, the resulting graph would become the CDAWG. However, the key discovery in this paper is not just the use of equivalence classes but the grid structure itself and its connection to the suffix trees, which has not been explored in previous works. The grid structure provides a powerful framework for organizing and querying these classes.

Recall the definition of Suffix Trees. Given a text \(T\), let \(\texttt{PreTree}(T)\) be the suffix tree \(\mathcal{T}(T)\), we have the following lemma.

The notation \(v_{B,i}\) will be used throughout the paper. The following corollary follows:

By 1, the relationship between blocks sharing a column indicates an ancestor-descendant relationship on \(\texttt{PreTree}(T)\). Furthermore, if they are adjacent, they have a parent relationship. We further map such relationships onto the grid by adding directed edges. In 3, the blocks \(B_x\), \(B_y\) and \(B_z\) correspond to the nodes \(\{x_1,x_2,x_3\}\), \(\{y\}\) and \(\{z\}\), respectively. The solid black arrows represent the edges in \(\texttt{PreTree}(T)\). [tab:relation] shows detailed information about these nodes and edges.

Similarly, we build one other tree \(\texttt{SufTree}(T)\) to help formalize the relationship between blocks sharing columns, which maintains substrings with common starting positions. Specifically, we build a Suffix Tree of \(\mathsf{rev}(T)\). Then, for each node \(u\), we reverse every string in \(\texttt{str}(u)\). We denote the tree as \(\texttt{SufTree}(T)\). The \(\texttt{SufTree}(T)\) with \(T = \texttt{abbab}\) is shown in 4. For example, \(\texttt{str}(x_2)=\{\texttt{abba},\texttt{bba},\texttt{ba}\}\) (after reversion).

The proof is similar to 3’s. The notation \(u_{B,j}\) will also be used throughout the paper. We have the following corollary similar to 1.

By 2, the relationship between blocks sharing a row indicates an ancestor-descendant relationship on \(\texttt{SufTree}(T)\). Furthermore, if they are adjacent, they have a parent relationship. We further map such relation onto the grid by adding directed edges, shown in 4. By 2 and 1, we have the following lemma.

The proofs of 1 2 3 5 can be found in 6.

Now, we are ready to formally introduce the Basic Substring Structure \(\mathtt{BASS}(T)\) of a given text \(T\), which consists of the following components:

• Two modified suffix trees \(\texttt{SufTree}(T)\), \(\texttt{PreTree}(T)\) and their mapping edges on \(G\).

• \(\texttt{left}_B, \texttt{right}_B, \texttt{top}_B\), and \(b_{\texttt{left}_B} \leq b_{\texttt{left}_B+1} \leq \ldots \leq b_{\texttt{right}_B}\) for a representative block \(B\) in each equivalence class;

• A data structure that locates a given substring \(T[l,r]\)’s equivalence class and its position within the block in \(O(1)\) time.

By 5, \(\mathtt{BASS}(T)\) takes up to \(O(n)\) memory.

3.4 Optimal Algorithm for Occurrence Counting↩︎

After building \(\mathtt{BASS}(T)\), we can mark only \(O(d)\) points to answer \(\mathrm{\small Count}\) query, optimized from the algorithm mentioned in 3.1. Recall the naive algorithm to answer \(\mathrm{\small Count}(l, r)\). We have \(\mathrm{\small Count}(l, r) = \sum_{i=l}^r \sum_{j=i}^r \mathbb{1} \{T[i, j] \in \mathcal{D}\}\). We use partial sums on BASS to optimize the above algorithm. Define \[\texttt{PreCount}(T[i, j]) = \sum_{k=i}^j \mathbb{1} \{T[i, k] \in \mathcal{D} \}\text{, } \texttt{SubCount}(T[i, j]) = \sum_{k=i}^j \texttt{PreCount}(T[k, j]).\] We can see that \(\mathrm{\small Count}(l, r)\) is equal to \(\texttt{SubCount}(T[l, r])\). However, storing these values for all substrings \(T[i,j]\) is expensive, so we store the following in the data structure:

1. \(\texttt{SubCount}(T[i,j])\) for strings located at the left border of each distinct block \(B\).

2. Partial sums of \(\texttt{PreCount}(\texttt{maxstr}(\texttt{parent}(v_{B,i})))\) for \(\texttt{left}_B\leq i\leq \texttt{right}_B\) for each distinct block \(B\).

3. A static 2D range counting data structure built on pattern grid cells in \(B\).

Queries can be answered through the following lemma:

The first term is already stored in the data structure, as \(\texttt{maxstr}(\texttt{parent}(u_{B,r}))\) is on the left border. The second term can be computed in constant time by the partial sums. The last term is handled by the static 2D range counting data structure.

Now we show how to preprocess these values efficiently. First, locating patterns in BASS costs \(O(d)\) time. Then, we adopt the following result from [47] to construct the 2D range counting data structure:

To preprocess the remaining information, we need to preprocess \(\texttt{PreCount}(\texttt{maxstr}(v))\) for all nodes \(v\in \texttt{PreTree}(T)\), then do a partial sum, and compute \(\texttt{SubCount}(\texttt{maxstr}(u))\) for all node \(u\in \texttt{SufTree}(T)\). First, \(\texttt{PreCount}(\texttt{maxstr}(v))\) is the number of patterns that is a prefix of \(\texttt{maxstr}(v)\), so it can be computed by getting the number of patterns located on each node of \(\texttt{PreTree}(T)\) and summing up these values along the edges between the root and \(v\). Computing \(\texttt{SubCount}(\texttt{maxstr}(u))\) is a bit more difficult. We also use the equation of 7. The first two terms can be computed in \(O(1)\) time after taking a partial sum on \(\texttt{PreCount}\). For the last term \(C\), notice that all \(\texttt{maxstr}(u)\) in a block \(B\) have the same and smallest \(l\)-coordinate, \(\texttt{left}_B\). Thus, the answer to the 2D range counting query is the number of patterns on or below the line of \(u\) in block \(B\). Consequently, after preprocessing the number of patterns on each node of \(\texttt{SufTree}(T)\), values of \(\texttt{SubCount}(\texttt{maxstr}(u))\) in a block \(B\) can be computed in time linear to the height of the block. Thus, preprocessing costs \(O(n+d\sqrt{\log n})\) time in total. Putting pieces together, we have the following theorem:

Moreover, we can further prove that our algorithm is equivalent to 2D range counting.

On the other hand, the optimal query time complexity for the 2D range counting problem is \(O(\frac{\log n}{\log\log n})\) when the data structure has a size of \(\tilde{O}(n)\) [41]. Consequently, our query time for Count\((l,r)\) queries is optimal. Moreover, the preprocessing time of \(O(d\sqrt{\log n})\) is currently the state-of-the-art in this field.

The proofs of 7 3 can be found in 6.

4 On Querying Distinct Patterns↩︎

In this section, we discuss the CountDistinct queries, answering the open question from [30] affirmatively. To answer CountDistinct queries, we convert them into a data structure problem using BASS and Count queries in 3.4. Our main result is as follows:

4.1 Problem Decomposition↩︎

Given a text \(T\), we consider \(\texttt{PreTree}(T)\) of \(\mathtt{BASS}(T)\). For each node \(u\) in \(\texttt{PreTree}(T)\), define \(f_u=\texttt{PreCount}(\texttt{maxstr}(u))\), counting the number of unique patterns in \(\mathcal{D}\) that can be recognized by \(u\) itself and the ancestors of \(u\) in \(\texttt{PreTree}(T)\). We also define a trie \(\texttt{Trie}(T[l, r])\) built on all suffixes of \(T[l, r]\). For a node \(u\) of the trie, let \(\texttt{str}'(u)\) be the string formed by the path from the root to \(u\). We define \(f'_u=\texttt{PreCount}(\texttt{str}'(u))\). Now, we have the following lemma that calculates \(\mathrm{\small CountDistinct}(l, r)\) on \(\texttt{Trie}(T[l, r])\):

We have divided the CountDistinct queries into two parts, \(A_1\) and \(A_2\). Now, we further explain what they are. To assist, we define the following key position:

With the definition of the key position, we can show that \(A_1\) can be computed as follows:

Then, \(A_2\) can be defined on \(\texttt{PreTree}(T)\) with the following lemma:

Combining 8 with 9 and 10, we get rid of the auxiliary trie and obtain:

To efficiently answer \(\mathrm{\small CountDistinct}(l, r)\), we need: (1) Find the key position \(\mathtt{pos}\). (2) Compute \(\mathrm{\small Count}(l,r)\) and \(\mathrm{\small Count}(\mathtt{pos}+ 1, r)\) by the algorithm in 3.4. (3) Compute \(A_2=\sum_{u\in \texttt{PreTree}(T), \mathtt{cnt}_u \geq 1} (\mathtt{cnt}_u-1)f_u\). In 4.2, we discuss the solutions to (1). (3) is discussed in detail in 4.3.

The proofs of 8 9 10 can be found in 6.

4.2 Finding Key Positions↩︎

Recall the definition of key positions: \(T[\mathtt{pos}, r]\) occurs exactly once in \(T[l,r]\), which means that the previous occurrence of \(T[\mathtt{pos}, r]\) has an end position smaller than \(l+r-\mathtt{pos}\). Thus, we define \(a_0^{(r)}(t)\) to be the end position of the last occurrence of the string \(t\) in \(T[1,r]\) (\(0\) if no occurrence). By definition, \(\mathtt{pos}\) is the largest number that has \(a_0^{(r-1)}(T[\mathtt{pos},r])<l+r-\mathtt{pos}\). Consider each node \(u\) in \(\texttt{SufTree}(T)\). Since all strings in \(\texttt{str}(u)\) share the same end positions, these strings have the same value of \(a_0^{(r)}(t)\) for every fixed \(r\). So we can regard \(a_0^{(r)}(t)\) as a variable attached to each node of \(\texttt{SufTree}(T)\), and we define \(a^{(r)}(u)=a_0^{(r)}(\texttt{maxstr}(u))\).

Now we show how to find the key position for a query CountDistinct\((l,r)\) if \(a^{(r)}(u)\) is maintained for all \(0\leq r\leq n\) and \(u\in \texttt{SufTree}(T)\). Let \(x_r\) be the node that \(T[1,r]\in \texttt{str}(x_r)\).

4.2.1 Data Structure↩︎

Now we introduce a data structure that supports finding the node \(y\) stated in 12 for a given query range \([l,r]\). We focus on the difference between \(a^{(r-1)}\) and \(a^{(r)}\). The changes take place in strings having a new occurrence, that is, they are a suffix of \(T[1,r]\). We have \[a^{(r)}(u)=\begin{cases} r & u\text{ is on the path from the root to } x_r\\ a^{(r-1)}(u) & \text{otherwise.} \end{cases}\] Then, we define the following events to characterize the difference between \(a^{(r-1)}\) and \(a^{(r)}\).

Then, the following lemma shows that all these changes (for \(r=1,2,\dots,n\)) can be represented by a near-linear number of events. We utilize the Link-Cut Tree [48] here.

These sets of events give us enough information to recover all the values of \(a^{(r)}(u)\). When querying the key position, we only care about the values of \(a^{(r-1)}(u)\) for \(u\) on the path from the root to \(x_r\), and these values are stored by those \(j\) in events \((i,j,u,v)\in E_r\). We now show how to find the key position by 12 when given \(E_r\). The procedure has two steps. The first step is to find the node \(y\) with the smallest depth that satisfies \(a^{(r-1)}(y)-\texttt{len}(y)+1<l\). Note that the value of \(a^{(r-1)}(y)\) decreases on the path from the root to \(x_r\) because every time the longer substring occurs, the shorter substring also occurs. Thus, \(a^{(r-1)}(y)-\texttt{len}(y)+1\) also decreases on the path from the root to \(x_r\). Consequently, we can use a binary search on \(E_r\) to locate \(y\). The second step is to find \(\mathtt{pos}\) when given \(y\), which is a constant-time evaluation. Overall, combined with 12, we have the following lemma:

The proofs of 12 13 can be found in 6.

4.3 Computing \(A_2\)↩︎

Recall that \(A_2=\sum_{u\in \texttt{PreTree}(T), \mathtt{cnt}_u>1} (\mathtt{cnt}_u-1)f_u\), since \(f_u\) is fixed by the dictionary \(\mathcal{D}\) and does not depend on the query range \([l,r]\), the challenge of computing \(A_2\) is to maintain the values of \(\mathtt{cnt}_{u}\) for all nodes in \(\texttt{PreTree}(T)\) and different query ranges. Similarly, we make use of the sets of events \(E_1, E_2,\dots, E_n\) defined in 13, but on \(\texttt{PreTree}(T)\). Specifically, since the substrings in \(\texttt{str}(v)\) for \(v\in \texttt{PreTree}(T)\) have the same starting positions, we define \(b^{(l)}(v)\) to be the start position of the first occurrence of \(\texttt{maxstr}(v)\) in \(T[l,n]\) (\(n+1\) if no occurrence). And, the difference between \(b^{(l+1)}\) and \(b^{(l)}\) is described by the event set \(F_l\). Formally, we define the events again:

And after defining \(x_l\) to be the node such that \(T[l,n]\in \texttt{str}(x_l)\), we present the following:

Let \(A_2(l,r)\) represent the value of \(A_2\) when the query range is \([l,r]\). Assuming that we already know the value of \(A_2(l+1, r)\), we consider how to derive the value of \(A_2(l, r)\). The difference comes from the substrings that occur in \(T[l,r]\) but not in \(T[l+1,r]\), changing the value of \(\mathtt{cnt}\). Assume that we have already maintained the values of \(\mathtt{cnt}\) for every node in \(\texttt{PreTree}(T)\) when the query range is \([l+1,r]\). For an event \((i,j,u,v)\in F_l\), we consider how it changes the values of \(\mathtt{cnt}\). During the event, we will change the value of \(b^{(l+1)}(x)\) from \(j\) to \(i\) for all vertices \(x\) on the path from \(u\) to \(v\), meaning that some of the vertices \(x\) may recognize substrings in \(T[l,r]\) while they recognize no substrings in \(T[l+1,r]\). This possibly changes the values of \(\mathtt{cnt}_x\) for the vertices \(x\) in the path from \(\texttt{parent}(u)\) to \(\texttt{parent}(v)\).

Now we know that when moving the query range from \([l+1,r]\) to \([l,r]\), some of the values of \(\mathtt{cnt}\) increase by \(1\). Recall that \(A_2=\sum_{u\in \texttt{PreTree}(T),\mathtt{cnt}_u> 1} (\mathtt{cnt}_u-1)f_u\). Thus, \(A_2(l,r)\) is equal to \(A_2(l+1,r)\) plus the sum of \(f_{\texttt{parent}(x)}\) for those \(x\) whose \(\mathtt{cnt}_{\texttt{parent}(x)}\) increased and with \(\mathtt{cnt}_{\texttt{parent}(x)}\geq 2\). By the following lemma, we show that, for a single event, although multiple \(\mathtt{cnt}_{\texttt{parent}(x)}\) increased, only one \(\mathtt{cnt}_{\texttt{parent}(x)}\) can have \(\mathtt{cnt}_{\texttt{parent}(x)}\geq 2\).

Thus, the only possible \(\mathtt{cnt}_{\texttt{parent}(x)}\geq 2\) is at the top of the path, the node \(\texttt{parent}(v)\). The following lemma describes when \(\mathtt{cnt}_{\texttt{parent}(v)}\geq 2\) is true:

4.3.1 Final Construction↩︎

Now we conclude the formula for \(A_2\). For \(l=n,n-1,\dots,1\), we perform the following:

1. Sort events in \(F_l\) by the order of the paths from \(x_l\) to the root.

2. Let \(A_2(l,r)\leftarrow A_2(l+1,r)\) for all \(l+1\leq r\leq n\) and \(A_2(l,l)\leftarrow 0\).

3. For all adjacent events \((i,j_0,u_0,v_0)\in F_l\) and \((i,j_1,u_1,v_1)\in F_l\) where \(u_1=\texttt{parent}(v_0)\), let \(A_2(l,r)\leftarrow A_2(l,r)+f_{u_1}\) for all \(r\in [j_1+\texttt{len}(u_1), j_0+\texttt{len}(u_1))\).

By previous lemmas, we prove that the correct value of \(A_2(l,r)\) is obtained after this procedure. Since the total number of events is \(O(n\log n)\), the above process can be maintained by \(O(n\log n)\) range additions with persistent data structures [49]: With a persistent segment tree, we answer each \(A_2\) query in \(O(\log n)\) time. We have 19 for computing \(A_2\).

The proofs of 16 17 18 can be found in 6.

4.4 Conclusion↩︎

Applying 14 and 19 to the algorithm scheme discussed in 4.1, we obtain the results of [CD-res]. In the study by Charalampopoulos et al. [30], the authors examined the specific scenario where the dictionary comprises square strings. They demonstrated an algorithm that achieves a query time of \(O(\log n)\) with space and preprocessing time complexities of \(O(n\log^2 n)\). Our algorithm matches this. Furthermore, when the dictionary consists of all the distinct substrings of \(T\), computing \(A_1\) is straightforward since the result for Count\((l,r)\) queries is given by \(\frac{(r-l+1)(r-l+2)}{2}\). In addition, \(A_2\) can be obtained by the algorithm above since \(f_u=\texttt{len}(u)\) is easy to compute. Consequently, CountDistinct\((l,r)\) queries can be resolved in \(O(\log n)\) time, utilizing \(O(n\log^2 n)\) space and preprocessing time.

5 More Applications↩︎

5.1 Exists and Report↩︎

There are two more fundamental types of queries under the internal setting: Exists and Report. While previous results already approach nearly optimal efficiency, we provide alternative algorithms with our proposed BASS.

5.1.1 Exists↩︎

First, we consider Exists\((l,r)\) queries, determining if there exists a pattern from \(\mathcal{D}\) that occurs in \(T[l,r]\). Our algorithm performance is formally stated as follows:

Our algorithm for Exists\((l,r)\) queries works in a similar fashion to Count. Recall that in 3.4, we can compute \[\begin{align} \sum_{i = l}^r \sum_{j = i}^r \mathbb{1} \{T[i, j] \in \mathcal{D} \land T[i, j] \notin B\} \end{align}\]

in \(O(1)\) time after \(O(n + d)\) preprocessing, where \(B\) is the block to which \(T[l, r]\) belongs. If this value is nonzero, the algorithm returns with positive validation; otherwise, \(\mathrm{\small Exists}(i, j) = \texttt{True}\) if and only if there exists \([i, j] \subseteq [l, r]\) such that \(T[i, j] \in \mathcal{D}\) and \(T[i, j] \in B\). It suffices to show how the existence of such \([i, j]\) can be decided in \(O(1)\) time given \([l, r]\).

To solve this, we consider each equivalence class in \(\mathtt{BASS}(T)\) independently. Similar to 3.4, we only need to consider an arbitrary block of this class. By regarding the pattern cells in the block as \(m\) normalized points in the 2D plane, this problem is thus equivalent to the following:

By precomputing the values of \(\min_{(x_i, y_i): x_i \geq v} y_i, \forall v \in [1, m]\) in \(O(m)\) time, each query to this problem can be answered in \(O(1)\) time. Recall that the sum of \(m\) for all equivalence classes is \(O(d)\). We thus prove [theo:exist].

5.1.2 Report↩︎

Then, we answer Report\((l,r)\) queries, which reports all occurrences of all patterns of \(\mathcal{D}\) in \(T[l,r]\). Our algorithm performance is formally stated as follows:

Our algorithm for Report consists of two parts:

1. We compute a set \(\mathcal{R}\) consisting of all indices \(j \in [l, r]\) such that there exists a pattern in \(T[l, r]\) with the end position \(j\).

2. For each \(j\) in \(\mathcal{R}\), we report a set \(\mathcal{L}(j)\) of the start positions \(i\) such that \(T[i, j]\) is a pattern.

Our goal is to finish the first part in \(O(|\mathcal{R}|)\) time and the second part in \(O(|\mathcal{R}|+\sum_{j\in \mathcal{R}} |\mathcal{L}(j)|)\) time. In this way, the total query time will be \(O(x)\), and [theo:report] is achieved.

5.1.2.1 Reporting \(\mathcal{L}(j)\).

We first consider the second part. Similar to 3.4, for each equivalence class \(C\) in \(\mathtt{BASS}(T)\), it suffices to consider an arbitrary block \(B\). For each block \(B\) considered, we precompute the following values for each row \(j\) of \(B\): (1) all pattern grid cells \(T[i, j] \in \mathcal{D}\) in row \(j\) of \(B\) in the increasing order of \(i\) and (2) the leftmost pattern grid cell \(T[i, j] \in \mathcal{D} \setminus B\) that is in row \(j\) and to the right of \(B\) (2).

By 5, the total number of rows over all distinct blocks is \(O(n)\), so we can compute all the above information in \(O(n + d)\) time. With these precomputed values, we can report the start positions in \(\mathcal{L}(j)\) by first locating the block of \(T[l, j]\) and then reporting the pattern grid cells in row \(l\) from left to right, within time \(O(1)\) for each pattern. This exactly gives the \(O(|\mathcal{R}| + \sum_{j \in \mathcal{R}} |\mathcal{L}(j)|)\) time complexity in total for the second part.

5.1.2.2 Finding \(\mathcal{R}\).

Now, we focus on how to find \(\mathcal{R}\) efficiently. Recall that for each row \(j\), \(j \in \mathcal{R}\) if and only if there exists a start position \(i (l \leq i \leq j)\) such that \(T[i, j]\) is a pattern. To check this in \(\mathtt{BASS}(T)\), we may first locate the cell \(T[l, j]\), and then see whether there exists a pattern grid cell \((i, j)\) on the right of \((l, j)\). Similar to the process of finding \(\mathcal{L}(j)\)s, for a fixed substring \(T[l, j_1]\) that has a pattern as its suffix, we can maintain the preceding row \(j_2 < j_1\) in the column \(l\) such that \(T[l,j_2]\) also has a pattern as its suffix. However, this might take \(\Theta(n^2)\) time and space.

To speed up the above process, we record the preceding equivalence class instead of the row. For each equivalence class \(C\), we still consider only one of its blocks \(B\) similar to 3.4. We only maintain the “predecessor” in a different block for each column \(i\) in \(B\), which only takes \(O(n)\) space by 5. Formally, given a block \(B\) and a column \(i\) in \(B\), we will maintain the top row \(j\) satisfying (1) \(j\) is in a block under \(B\) and (2) there exists a \(k \in [i, j]\) such that \(T[k, j] \in \mathcal{D}\). Dynamic programming on the grid can compute this in \(O(n + d)\) time.

With this information, we can find the set of blocks that contain at least one row in \(\mathcal{R}\). In addition, each row in \(\mathcal{R}\) occurs in exactly one block of this set. This takes \(O(|\mathcal{R}|)\) time by first locating the block that \(T[l, r]\) belongs to and then iterating rows with the fixed column \(l\). By doing so, it remains to find the rows \(r\) that belong to \(\mathcal{R}\) for each of these blocks.

By 5, given a block \(B\), we may maintain the rightmost pattern grid cell \(T[i, j] \in \mathcal{D}\) for each row \(j\;(l \leq j \leq r)\) in \(B\) in \(O(n+d)\) time. Denote this by \(h_j\), so that row \(j\) is in \(\mathcal{R}\) if and only if \(l \leq h_j\). Now, it suffices to compute the set \(S_B\) of indices \(j \in [b_l, \min(\texttt{top}_B, r)]\) that satisfies \(h_j \geq l\) in \(O(|S_B|)\) time. If we view \((j, h_j)\) as points of a 2D plane, this is exactly the \(3\)-sided range reporting problem. This is studied in [50], and is efficiently solved by Range Minimum Query (RMQ) algorithms [51] with the desired performance.

5.2 ReportDistinct↩︎

Compared to the Report query that finds all occurrences in a substring, ReportDistinct queries only report every pattern once. In [31], it achieves \(O(\log n + x)\) query time with \(O(n \log n + d)\) preprocessing, where \(x\) denotes the length of the output. With BASS, we improve the query time to \(O(1+x)\). Both previous works and our algorithm take \(O(n + d)\) memory. The formal theorem is as follows:

Let \(D\) denote the set of patterns that occur in \(T[l,r]\). The key idea is to find the patterns in \(D\) that are not suffixes of any longer pattern in \(D\). We denote this set as \(S\). With \(S\), we can locate and report other patterns in \(\texttt{SufTree}(T)\) in \(O(1 + x)\) time by the following lemma.

We determine \(S\) by computing the following two subsets of \(D\). For each \(i\in [l, r]\), let \(p_i\) be the longest pattern suffix of \(T[l, i]\), recognized by node \(u_i\in \texttt{SufTree}(T)\). Let \(v_i\) denote the node recognizing \(T[l, i]\). Then, the first subset is: \[S_1 = \{ p_i \mid u_i = v_i, i\in [l,r]\}.\] Let \(q_i\) be the longest pattern suffix of \(T[l, i]\) recognized at an ancestor of \(v_i\). Then, we define the second subset as: \[S_2 = \{ q_i \mid q_i \text{ occurs exactly once in } T[l, i], i\in [l,r]\}.\] It suffices to find \(S_1\) and \(S_2\) efficiently due to the following lemma:

5.2.0.1 Finding \(S_1\)

Let \(\mathcal{Q}=\{i\mid u_i=v_i, i\in [l,r]\}\). \(\mathcal{Q}\) resembles the set \(\mathcal{R}\) in Report\((l,r)\) queries, but \(\mathcal{Q}\) includes indices \(i\) only if the pattern suffix of \(T[l, i]\) is in the same block as \(T[l, i]\) in BASS. Thus, by precomputing the rightmost occurrence of patterns in each row of every block, \(\mathcal{Q}\) can be efficiently determined using a \(3\)-sided range reporting algorithm [50].

Once \(Q\) is identified, we compute \(S_1'\), an extension of \(S_1\), as follows: \(S_1'\) contains all patterns that are suffixes of \(T[l,i]\) and lie in the same block as \(T[l,i]\) for all \(i\in \mathcal{Q}\). We have \(S_1\subseteq S_1'\), and since each row in the BASS corresponds to distinct strings, patterns in \(S'_1\) are unique. To construct \(S'_1\), we iterate over patterns in row \(i\) (for each \(i\in \mathcal{Q}\)) from right to left, terminating when a pattern is no longer a suffix of \(T[l, i]\). This process runs in \(O(|S'_1|)\) time, ensuring the total cost remains within \(O(1+x)\), where \(x\) is the output size.

5.2.0.2 Finding \(S_2\)

For each node \(u\) in \(\texttt{SufTree}(T)\), we define \(z_u\) as the longest pattern that is a suffix of \(\texttt{maxstr}(\texttt{parent}(u))\) (\(\epsilon\) if not exist). Furthermore, we define \(w_u\) as the node in \(\texttt{SufTree}(T)\) that recognizes \(z_u\). Since \(q_i\) is not recognized by the same node as \(T[l, i]\), \(q_i\) depends only on \(v_i\)—the node that recognizes \(T[l, i]\), and satisfies \(q_i=z_{v_i}\). Despite that the indices \(l, i\) may be different, whether \(z_{v_i}\) appears in \(T[l, i]\) once only depends on the string \(T[l, i]\) itself. And, for strings recognized by the same node \(u\in \texttt{SufTree}(T)\), the longer the string, the higher the chance that \(z_{v_i}\) has another occurrence. Thus, for each node \(u\in \texttt{SufTree}(T)\), there is a boundary in its BASS row, where only the substrings on its right contain \(z_u\) exactly once.

To determine the boundary, we use the array \(a^{(r)}(\cdot)\) from 4.2. Specifically, \(z_{u}\) appears once in a string \(T[j,k]\in \texttt{str}(u)\) if and only if \(a^{(k-1)}(w_{u})-|z_{u}|+1<j\). This inequality checks whether the previous occurrence of \(z_{u}\) starts before \(j\). We can check for an arbitrary occurrence of strings in \(\texttt{str}(u)\). The value of \(a^{(k-1)}(w_{u})\) can be retrieved from the event set \(E_{k-1}\) from 13, yielding an \(O(n\log n)\) preprocessing time.

Finally, indices \(i\) contributing to \(S_2\) correspond to the positions where \(T[l, i]\) lies to the right of the precomputed boundary for that row. Using 3-sided range reporting (similar to \(\mathcal{R}\) in Report\((l,r)\) queries and \(\mathcal{Q}\) in the previous \(S_1\) part), \(S_2\) is determined in \(O(|S_2|)\) time.

5.3 Range Longest Common Substring↩︎

Consider the following internal query problem related to the longest common substrings (LCS).

By using BASS technique, we have the following result.

This improves the previous best result of \(O(\log n)\) query time [42] and achieves optimal performance.

We start presenting our data structure by introducing an auxiliary string \(A\). Let \(A = Sc_1Sc_2T\) be a string formed by concatenating \(S, c_1, S, c_2, T\), where \(c_1, c_2\) are distinct characters that do not exist in either \(S\) or \(T\). We construct \(\mathtt{BASS}(A)\). Given that \(c_1\) (or \(c_2\)) occurs only once in \(A\), every string containing \(c_1\) or \(c_2\) should belong to the same block as the entire string \(A\). Consequently, every substring of \(S\), which occurs in \(A\) at least twice, belongs to a block different from \(A\). Equivalently, we have the following lemma:

Now, we have the following, where \(B\) is the block that \(A[l, r]\) belongs to: \[\begin{align} \mathrm{\small LCS}(l,r) &=\begin{cases} \;\;\;\;\;\;\;r-l+1 & A[l,r] \text{ occurs in } S\\ \underset{\substack{l \leq a \leq b \leq r \\ A[a, b] \in S \text{ and } A[a, b] \notin B}}{\max} \{b - a + 1\} & \text{otherwise} \end{cases} \end{align}\]

One observation is that the optimal \((a, b)\) above must be on some blocks’ top or left border. During the preprocessing phase, we store the answer \(\mathrm{LCS}(l, r)\) for every \((l, r)\) that is on the border of a block. Since we only need to store the answer for one arbitrary block for each equivalence class, the total information we need is \(O(|A|)\).

What remains is that given the information of the blocks to the down or right of \(B\), after some preprocessing within time linear in the perimeter of \(B\), we need to compute \(\mathrm{\small LCS}(l,r)\) in \(O(1)\) time. This would give a unified approach for answering queries in constant time, as well as precomputing the required information in linear time.

The answers on the bottom or right border are easy to retrieve. And, for a substring \(t\) on the top or left border of \(B\), the answer is the maximum of the answer of the substrings that occurs in \(t\) and on the bottom or right border of \(B\). Since the block is staircase-shaped by 1, if we regard all substrings on the bottom or right border as a sequence, we only need to take the maximum of the answer inside an interval.

As we know that range maximum queries can be answered in constant time by a \(O(n)\) time constructible data structure, our algorithm can be done in linear time. When query, similarly, we only need to answer a range maximum query within that block, costing only constant time.

In [42], another problem is also proposed: Given two strings, \(S\) and \(T\), of lengths up to \(n\), the task is to construct a data structure that computes the LCS between any prefix or suffix of S and any prefix or suffix of T. By employing BASS, we can develop a data structure of size \(O(n\log\log n)\), which answers such queries in \(O(\log\log n)\), outperforming the previous best-known result. We believe BASS offers deeper insight into the relationships among substrings and will lead to further applications.

6 Omitted Proof↩︎

The following proves there is only one longest substring \(s\) for any substring \(t \in T\), which indicates that the extension is well-defined.

References↩︎

---

1. Part of this work was done while at Georgia Tech and the University of Waterloo.↩︎

2. The \(\tilde{O}(\cdot)\) notation suppresses \(\log^{O(1)} n\) factors for inputs of size \(n\).↩︎