Longest Common Extension of a Dynamic String in Parallel Constant Time

Daniel Alexander Albert · 2026

Read Longest Common Extension of a Dynamic String in Parallel Constant Time by Daniel Alexander Albert (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-12696.txt.

Introduction

Daniel Albert presents a dynamic parallel constant-time algorithm for longest common extension queries. An LCE query finds the longest shared prefix or suffix at two positions. The structure supports character insertions and deletions. It runs on a common CRCW PRAM with work scaling as n to a small power. A synchronizing sets hierarchy answers substring equality queries. Those answers feed LCE queries. Stored information may lag by up to log n log-star n updates. Two applications follow: Dyck language membership and square maintenance.

Catalog record

CREATORDaniel Alexander Albert
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE132571
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.12696

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Longest Common Extension of a Dynamic String in Parallel Constant Time Daniel Alexander Albert Abstract A longest common extension (LCE) query on a string computes the length of the longest common suffix or prefix at two given positions. A dynamic LCE algorithm maintains a data structure that allows efficient LCE queries on a string that can change via character insertions and deletions. A dynamic parallel constant-time algorithm is presented that can maintain LCE queries on a common CRCW PRAM with 𝒪 ⁡ ( n ϵ ) \mathcal{O}(n^{\epsilon}) work, for any ϵ > 0 \epsilon>0 . The algorithm maintains a string synchronizing sets hierarchy, which it uses to answer substring equality queries, which it in turn uses to answer LCE queries. To achieve constant runtime, the algorithm allows parts of its information to become outdated by up to log ⁡ n ​ log ∗ ​ n \log n\log^{*}n updates. It answers queries by combining this slightly outdated information with a list of the recent changes. Two applications of this dynamic LCE algorithm are shown. Firstly, a dynamic parallel constant-time algorithm can maintain membership in a Dyck language D k , k > 0 D_{k},k>0 with 𝒪 ⁡ ( n ϵ ) \mathcal{O}(n^{\epsilon}) work for any ϵ > 0 \epsilon>0 . Secondly, a dynamic parallel constant-time algorithm can maintain squares with 𝒪 ⁡ ( n ϵ ) \mathcal{O}(n^{\epsilon}) work for any ϵ > 0 \epsilon>0 . TU Dortmund University, Germany [email protected] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003809.10010170¡/concept_id¿ ¡concept_desc¿Theory of computation Parallel algorithms¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003809.10010031.10010032¡/concept_id¿ ¡concept_desc¿Theory of computation Pattern matching¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003777.10003787¡/concept_id¿ ¡concept_desc¿Theory of computation Complexity theory and logic¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ ccs Theory of computation Parallel algorithms ccs Theory of computation Pattern matching ccs Theory of computation Complexity theory and logic keywords Dynamic Strings, Work, Parallel Constant Time, Longest Common Extension, Longest Common Prefix † † runningtitle: Dynamic LCE in Constant Time † † runningauthor: D. Albert † † copyright: Daniel Albert 1 Introduction Answering longest common extension (LCE) queries is a fundamental problem that appears as part of many string algorithms. An LCE query determines, for two given indices i,j of a string S , the length of the longest common prefix ( LCP ) of S[i,|S|] and S[j,|S|] , or the length of the longest common suffix ( LCS ) of S[1,i] and S[1,j] . Background on LCE Queries LCE queries trace back to Landau and Vishkin [ 16 , 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 ( [ 16 , Section 4] and [ 24 ] ). 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 [ 12 , Theorem 2] , which runs in \mathcal{O}(\log^{2}n) time on \mathcal{O}(n/\log n) processors. This algorithm runs on the very restrictive EREW PRAM model. Shun improved this algorithm to run on \mathcal{O}(n/\log^{2}n) processors [ 21 , 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 [ 10 ] . 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 [ 8 ] . 1 1 1 Gawrychowski 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. Parallel Constant-Time Algorithms 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 [ 20 ] , 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 Contributions Our primary result is the following theorem. Theorem 1 . For any \epsilon>0 , there is a dynamic algorithm on a common CRCW PRAM that maintains a data structure for a string S with fixed maximum size n , where • the size of the data structure is in \mathcal{O}(n\log n\log^{*}n) , 2 2 2 The iterated logarithm \log^{*}n counts the number of times the logarithm (with base 2 ) has to be applied until the result is at most 1 . It grows extremely slowly, e.g. \log^{*}2^{65536}=5 . • the initialization for S=\epsilon runs in parallel constant time on \mathcal{O}(n\log n\log^{*}n) processors, • updates to the data structure after the insertion or deletion of a character are processed in parallel constant time on \mathcal{O}(n^{\epsilon}) processors, and • the LCE of two given indices is computed in parallel constant time on \mathcal{O}(n^{\epsilon}) processors. 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 [ 14 , 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 \mathcal{O}(n^{\epsilon}) processors. Related Work 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 [ 18 , 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 [ 18 ] ,

Read the complete text