Longest Common Extension of a Dynamic String in Parallel Constant Time

LCE queries trace back to Landau and Vishkin [14, Section 2.3], who use the name MAX-LENGTH for what we call the length of the LCP. Optimal LCE algorithms build a data structure for a given string which answers LCE queries in constant time. The first construction algorithm runs in linear time for constant alphabets ([14, Section 4] and [20]). Later algorithms achieve the same runtime even for integer alphabets [5].

These algorithms are sequential and run on a single processor. With parallel machines, we can find algorithms with shorter runtime at the cost of adding more processors.

An early parallel LCE algorithm is the skew algorithm by Kärkkäinen and Sanders [10, Theorem 2], which runs in $𝒪({\log }^{2}n)$ time on $𝒪(n/\log n)$ processors. This algorithm runs on the very restrictive EREW PRAM model. Shun improved this algorithm to run on $𝒪(n/{\log }^{2}n)$ processors [19, Theorem 3.6]. This algorithm is work-efficient, meaning that simulating it with just one processor is as efficient as the best known sequential algorithm.

These algorithms operate in the static setting. In the dynamic setting, we are looking for a data structure which can keep up with changes to the string. We are interested in dynamic problems where we can insert or delete single characters anywhere in the string. There has been some research on dynamic LCE algorithms on sequential machines.

Early work on dynamic strings was done by Gu, Farach and Beigel [8]. They studied the related dynamic text indexing problem. This problem is about maintaining a data structure for a changing string which can report all occurrences of a given pattern in the string. Gawrychowski et al. show an optimal data structure for a different related problem where updates and LCE queries run in logarithmic time, with high probability [7].¹¹1Gawrychowski et al. study a different but related problem and their algorithm is more powerful. The dynamic LCE problem is reducible to the problem in Gawrychowski et al. This reduction increases the runtime of queries from constant to logarithmic.

We study the problem of dynamic LCE queries in the context of parallel constant-time algorithms. We use the parallel computational model described by Shiloach and Vishkin [18], which since has become known as the common CRCW PRAM (see e.g. [6]). A common CRCW PRAM employs multiple parallel processors that access a shared memory. Multiple processors can access the same cell of memory concurrently, but concurrent writes are only allowed if all write the same value.

We study parallel algorithms where the maximum runtime over all processors is constant. Our measure for the complexity of such algorithms is the number of processors.

Our primary result is the following theorem.

A maximum size $n$ for the string is fixed at the initialization.

Our algorithm answers LCE queries using string synchronizing sets, which keep track of the occurrences of some substrings within the underlying string. Kempa and Kociumaka [12, Section 7] show a dynamic algorithm that maintains these sets. We modify this algorithm to run in parallel constant time, using techniques related to the so-called Muddling-Lemma [4].

As an application of Theorem 1, a common CRCW PRAM can maintain Dyck languages (Corollary 15) and squares (Corollary 16) in constant time on $𝒪(n^{ϵ})$ processors.

We already discussed related work on LCE queries. Here we go over some related work on dynamic parallel constant-time algorithms.

The study of dynamic parallel constant-time algorithms originated in the field of database theory. It traces back to the introduction of the complexity class DynFO by Patnaik and Immerman [16, Section 3.1]. DynFO contains dynamic problems where the actions required for processing updates and answering queries can be expressed as first-order formulae.

Patnaik and Immerman show that many relevant problems are in DynFO [16], like reachability on undirected graphs. Their conjecture that reachability on directed graphs is also in DynFO was later proven by Datta et al. [3].

Schmidt et al. study DynFO-algorithms to maintain membership queries for various classes of formal languages [17] via common CRCW PRAMs. The complexity class DynFO coincides with dynamic parallel constant-time algorithms on common CRCW PRAMs [9, Corollary 5.10]. The advantage of using PRAMs instead of first-order formulae to specify dynamic algorithms, as argued by Schmidt et al. [17], is that PRAM algorithms are usually easier to understand and PRAMs have a very clear and natural notion of work.

We first give an informal description of our algorithm in Section 2. The detailed description starts with preliminary definitions and auxiliary algorithms in Section 3. Section 4 describes how the algorithm stores its information. Section 5 explains how to answer queries with this information and Section 6 describes how to process updates. Section 7 shows two applications of Theorem 1, namely for maintaining Dyck languages and squares.

A good starting point for string synchronizing sets is the algorithm by Kociumaka et al. [13, Section 4]. We explain its ideas in the following.

Simply speaking, a string synchronizing set is a set of occurrences of substrings of a certain size with some useful properties. An occurrence of a substring is a sequence of positions so that the characters of the underlying string at these positions match the substring. Occurrences are typically represented by their first position and some identifier for the substring.

A string synchronizing set stores occurrences for some substrings. If any occurrence of a substring is stored, then all its occurrences need to be stored. This property is called consistency. Every position of the underlying string is covered by the first half of an occurrence and the total length of all occurrences is linear to the length of the underlying string. These properties are called density and sparseness respectively. Occurrences are assigned consistent names so that occurrences of the same substring have the same name.

Given a hierarchy of logarithmically many string synchronizing sets where the occurrence-length doubles with each level, an algorithm can decide efficiently if any two given segments are equal. To do so, it computes canonical coverings for both segments and checks if they match. A covering is a selection of occurrences from the synchronizing sets so that every position in the segment is covered by at least one occurrence. To compute a canonical covering, the algorithm selects, from each level in the synchronizing sets hierarchy, the first and last occurrences that lie entirely within the segment. See Table 1 for an example, where $B^1$ is the string synchronizing set with substring-length 1, $B^2$ with substring-length 2 and $B^4$ with substring-length 4. In the string $S$, every first position of an occurrence in $B^1,B^2,B^3$ is marked with the name assigned to that occurrence.

It is not hard to see that, thanks to consistency, two substrings are equal if and only if their canonical coverings match. The algorithm can compute and compare canonical coverings efficiently because a canonical covering consists of at most a logarithmic number of occurrences. The LCE is then computed with several queries for substring-equality.

The construction algorithm computes the synchronizing sets hierarchy via a hierarchy of decompositions. Each decomposition divides the underlying string into a sequence of factors. Unlike the string synchronizing sets, the factors may have different lengths, but can not overlap one another. These decompositions are computed in a bottom-up fashion, starting with the decomposition of singleton factors. Then follows a series of stages where each stage takes the current decomposition and merges factors to produce the next decomposition.

A stage first looks for and merges runs of identical factors. After this preparation, a stage merges each factor with some of its neighbors consistently, i.e., if the context around two factors is identical, then it produces the same merged factors. The context around a factor consists of that factor and a certain number of characters before and after that factor. The exact number of characters depends on the rule used to choose these merges. We do not look at the concrete rule used by Kociumaka et al. [13, Section 4.2]. The rule has to be consistent, have a small context, and each merge has to involve up to a constant number of factors.

The algorithm runs over a logarithmic number of stages. The topmost decomposition consists of only one factor for the entire string. The algorithm derives the string synchronizing sets from the decompositions hierarchy. For each level of the synchronizing sets hierarchy, it selects an appropriate decomposition from the hierarchy. Every factor in the decomposition is lengthened and becomes an occurrence in the synchronizing set.

Kempa and Kociumaka [12, Section 7] describe a dynamic algorithm that maintains a string synchronizing sets hierarchy. The algorithm is sequential and queries and updates run in poly-log-time. The dynamic algorithm stores the decompositions hierarchy and synchronizing sets hierarchy. The idea is that, for each update, it suffices to recalculate only small parts of these hierarchies. To achieve this, Kempa and Kociumaka had to ensure that each update affects only small parts of the hierarchies. To this end, they substitute the global sparseness criteria outlined above with local sparseness. Local sparseness demands that the total length of all occurrences within any part of the string is linear in the length of that part, within a ${\log }^{\ast }n$ factor.

To achieve local sparseness, Kempa and Kociumaka modify the processing of the stages. They modify the rule for choosing merges so that the merging of each factor depends only on a few factors around it.³³3This is stricter than demanding only consistency. For example, the algorithm in [13] first inspects the entire string to build a rule for merging factors, then applies that rule consistently. Changing one character might result in a different rule and lead to many changes in the resulting decomposition. With their modified rule, changing one character of the string affects only a small part of the decompositions and synchronizing sets. The dynamic algorithm can afford to recalculate the affected parts for each update.

We take the dynamic algorithm from Kempa and Kociumaka [12] and modify it so that updates and queries run in constant time. Our main challenge is that an update affects logarithmically many levels and it is unclear how the modifications could be computed in parallel constant time.

Our solution is a technique inspired by the so-called Muddling-Lemma [4]. The algorithm allows its data structure to become slightly outdated, i.e. the synchronizing sets do not match the current string, but the string as it was a certain number of updates ago. This technique gives the algorithm enough time to traverse the hierarchy sequentially when calculating the changes that result from an update, but makes queries slightly more complicated.

The processing of one update runs through all $\log n$ levels in sequence, taking $𝒪({\log }^{\ast }n)$ time per level. The algorithm divides this processing into $\log n{\log }^{\ast }n+1$ actions, each of which runs in constant time. It spreads the actions across the following updates, so that each following update advances the processing by one action. The changes that result from the $k$-th update are fully processed with the $(k+\log n{\log }^{\ast }n)$-th update. Each update computes its first action as well as $\log n{\log }^{\ast }n$ actions belonging to previous updates, all in parallel.

Due to this delayed processing, the lowermost decomposition is delayed by ${\log }^{\ast }n$ updates, the next level by $2{\log }^{\ast }n$ updates, and so on, with the topmost decomposition delayed by $\log n{\log }^{\ast }n$ updates. These delays carry over to the synchronizing sets.

Queries have to account for the fact that the information does not reflect the current string. The solution to this problem lies in the observation that there are only up to ${\log }^{\ast }n\log n$ individual positions with outdated information. The algorithm cuts queries at these positions, splitting it into a poly-logarithmic number of sub-queries. It answers each sub-query with the slightly outdated information, then compares the cut-out positions naïvely.

The first data structure stores the current string without delay in an instance $𝒮$ of DynamicMarkedString. It does not use the marks. Most of the other data structures represent the string as it was some number of updates ago.

The algorithm uses a record of the most recent updates to resolve outdated information. The record $ℛ$ is a compact sorted array that stores the most recent $\log n{\log }^{\ast }n$ updates. The entries in $ℛ$ store either that a character was inserted at some index or that at least one character was deleted between two indices. The entries are sorted by index. Each entry also stores the age of that change.

The algorithms uses a synchronizing sets hierarchy where the length of the substrings doubles with each level.

For each $\tau =2^z,z\in \mathbb{N},\tau \in [1,n]$, it stores a synchronizing set $(B^{\tau },f^{\tau })$ in an instance ${ℬ}^{\tau }$ of DynamicMarkedString, with some delay. The underlying string in ${ℬ}^{\tau }$ is the delayed string at that level. It marks every index $i\in B^{\tau }$ and annotates them with the name $f^{\tau }(i)$. It maintains forward- and backward-links for every index in ${ℬ}^{\tau }$ to the corresponding index in the current string $𝒮$. It supplements the synchronizing sets with an instance ${𝒩}_B^{\tau }$ of DynamicNames to maintains the names used by $B^{\tau }$.

The algorithm computes the synchronizing sets via a decompositions hierarchy of decompositions $D^{\mathrm{\ell }}$ for each $\mathrm{\ell }\in \{1,\mathrm{\dots },\log n\}$.

The algorithm maintains several properties for the decompositions $D^{\mathrm{\ell }}$ that mirror the properties of string synchronizing sets. The decompositions are consistent in the sense that, if a big enough substring around a factor also occurs somewhere else, there is a copy of that factor at that second occurrence as well. It furthermore maintains upper and lower bounds for the size of the factors. We prove these properties at a later point.

The instance ${𝒮}^{\mathrm{\ell }}$ of DynamicMarkedString stores the delayed string. It marks every first index of a factor in $D^{\mathrm{\ell }}$ and annotates them with the name of the factor. It maintains links between each index in ${𝒮}^{\mathrm{\ell }}$ and the corresponding index in the current string $𝒮$.

The instance ${𝒟}^{\mathrm{\ell }}$ of DynamicMarkedString also stores the decomposition. Unlike ${𝒮}^{\mathrm{\ell }}$, the underlying string is not the string for DynamicLce but the sequence of factor names in the decomposition $D^{\mathrm{\ell }}$. It marks every factor that has a different name than the factor before it. It maintains links between each factor name in ${𝒟}^{\mathrm{\ell }}$ and its starting index in ${𝒮}^{\mathrm{\ell }}$.

It uses the instance ${𝒩}_D^{\mathrm{\ell }}$ of DynamicNames to maintain consistent factor names for $D^{\mathrm{\ell }}$.

We first show that we can answer substring equality queries if fully up-to-date string synchronizing sets $(B^{\tau },f^{\tau })$ for each $\tau =2^z,z\in \mathbb{N},\tau \in [1,n]$ are available. For now, we assume that we also have, for each $(B^{\tau },f^{\tau })$, successor- and predecessor-links which point, for each index of $S$, to the closest occurrence in $B^{\tau }$.

Sketch. The algorithm first covers $S[i,i+m)$ with logarithmically many occurrences from the synchronizing sets hierarchy. It uses the successor- and predecessor-links to find, for each level $\tau$, the first and last occurrence at that level that lies entirely in $S[i,i+m)$. This produces a covering of $S[i,i+m)$, unless there are periodic prefixes or suffixes, which require some special handling. Then the algorithm looks at $S[j,j+m)$ and, if it can find the same covering there, concludes $S[i,i+m)=S[j,j+m)$. See the full version of this paper for a proof [1, Appendix B].

As mentioned above, the algorithm has to deal with the complication that it does not maintain fully up-to-date string synchronizing sets. Indeed there may be $\log n{\log }^{\ast }n$ positions where characters were recently inserted or deleted for which its information is outdated. Our solution is to cut the query at these positions into sub-queries which can be answered with the available information.

The algorithm first splits the query into sub-queries so that no sub-query contains recently changed indices. It creates a sub-query for the prefixes of $S[i,i+m)$, $S[j,j+m)$ up to but not including the first recorded change in either segment. Then, for every entry in the record $ℛ$, if the recorded change lies within $S[i,i+m)$, it creates a further sub-query that starts at the first unaffected index after that change and ends at the next change in either $S[i,i+m)$ or $S[j,j+m)$. It similarly creates sub-queries for changes in $S[j,j+m)$.

This results in $𝒪(ℛ)=𝒪(\log n{\log }^{\ast }n)$ sub-queries, which are answered in parallel using Lemma 6. Since the structures ${ℬ}^{\tau }$ are delayed, it is possible that the same character occupies different indices in $𝒮$ and ${ℬ}^{\tau }$, even if this position itself was not changed recently. The algorithm uses the links between each position in the current string $𝒮$ and their corresponding positions in the delayed structures ${ℬ}^{\tau }$ to match shifted indices.

The complexity of each sub-query is given in Lemma 6, but there is one caveat. In Lemma 6, we assumed that successor- and predecessor-links are precomputed and accessible with constant work, which is not true here. Instead the algorithm retrieves them from ${ℬ}^{\tau }$, which requires $𝒪(n^{\theta })$ processors per query for any $\theta >0$ (Lemma 3). For any given $ϵ>0$, we can choose $\theta$ such that the total number of processors overall is $𝒪(n^{ϵ})$.

Finally, alongside the sub-queries for unchanged segments, the algorithm checks single indices which were recently inserted and lie within $S[i,i+m)$ or $S[j,j+m)$ and compares them naïvely. There are at most $\log n{\log }^{\ast }n$ recently inserted indices. $◀$

The final step reduces LCE queries to substring equality queries.

The algorithm finds the length of the LCE via several substring equality queries with a binary-search-like approach, with arity $n^{ϵ}$ instead of two. Starting with the search range of all lengths $[1,n]$, it splits the search range into $n^{ϵ}$ same-sized segments at each step. It formulates one substring equality query per segment to determine which segment contains the LCE and becomes the next search range. This procedure terminates after $\frac{1}{ϵ}$ rounds. $◀$ The information described in Section 4 suffices to answer LCE-queries. It remains to show that the algorithm can maintain that information in parallel constant time on $𝒪(n^{ϵ})$ processors.

The decompositions $D^{\mathrm{\ell }}$ are arranged bottom-up along levels $\mathrm{\ell }\in \{1,\mathrm{\dots },\log n\}$. Updates traverse these levels in ascending order. The processing of an update is split into $\log n{\log }^{\ast }n+1$ actions $A(k,\mathrm{\ell },i)$, where $k$ counts the updates, $\mathrm{\ell }\le \lceil \log n\rceil$ the levels, and $i\le \lceil {\log }^{\ast }n\rceil$ the actions on a level. The actions of the $k$-th update are $\{A(k,0,0)\}\cup \{A(k,\mathrm{\ell },i)\mid \mathrm{\ell }\in [1,\log n],i\in [i,{\log }^{\ast }n]\}$. Actions are ordered lexicographically, i.e. if or . All of these actions processed sequentially in ascending order compute the changes that result from the $k$-th update.

The first action $A(k,0,0)$ updates the current string $𝒮$ and the record $ℛ$. The actions $A(k,\mathrm{\ell },1),\mathrm{\dots },A(k,\mathrm{\ell },{\log }^{\ast }n)$ together calculate the changes to level $\mathrm{\ell }$ of the decompositions hierarchy. They also update the synchronizing sets that belong to that level.

The algorithm only processes the very first action $A(k,0,0)$ immediately. Then, for each subsequent update, it advances the processing of this update by one further action. When update $k$ arrives, the algorithm thus processes the following actions in parallel (if they exist):

For a decomposition $D^{\mathrm{\ell }}$ and an update that affects index $i$, the affected segment is the sequence of factors $v_j,\mathrm{\dots },v_{j+k}$ in $D^{\mathrm{\ell }}$ that might be affected by that update. It is the part of the $D^{\mathrm{\ell }}$ that has to be recalculate for an update at index $i$. An important prerequisite of our algorithm is that this affected segment is small.

The relevant segment is the union of all factors that influence a factor in $v_j,\mathrm{\dots },v_{j+k}$. They are the factors the algorithms has to know to recalculate the affected segment.

This lemma establishes the context that affects each factor of the decomposition. It informs us that changes to one factor affect at most ${\log }^{\ast }n+9$ factors before and $5$ factors after it. To recalculate these affected factors, the algorithm only needs ${\log }^{\ast }n+14$ factors on both sides. We do not prove Lemma 9 yet because we have to present the algorithm first.