Pith. sign in

REVIEW 2 major objections 5 minor 45 references

Space-Efficient Construction of Compressed Suffix Trees

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A compressed suffix tree can be built directly from the Burrows-Wheeler transform using sublinear working space and near-linear time.

desk verdict The LCP and PLCP constructions are solid and the BWT merge is a real contribution, but Section 8's BPS topology construction omits leaf intervals, so Theorem 5's compressed suffix tree claim is not actually proven. read the letter →

arxiv 1908.04686 v1 pith:FL2SCFJW submitted 2019-08-12 cs.DS

Nicola Prezza , Giovanna Rosone This is my paper · ORCID
classification cs.DS MSC 68W32
keywords Burrows-WheelertransformcompressedsuffixtreeLCParrayPLCPbitvectorbalancedparenthesessuccinctworkingspacestringcollectionsBWTmerging
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper aims to show that all components of a compressed suffix tree—the LCP values, the PLCP bitvector, and the balanced-parentheses topology—can be derived directly from a Burrows-Wheeler transform in working space that is asymptotically smaller than the BWT itself. The key result is parameterized: for any $\epsilon$, the PLCP bitvector and the suffix tree topology are built in $\epsilon\cdot n\log\sigma + o(n)$ bits, with time $O(n(\log\sigma + \epsilon^{-1}\log\log n))$, and the resulting compressed suffix tree takes $n\log\sigma + 6n + o(n\log\sigma)$ bits. This closes a gap between previous algorithms, which required either $O(n\log\sigma)$ bits with linear time or $O(n)$ bits with $O(n\log n)$ time. The same techniques merge two BWTs of a string collection in $O(n\log\sigma)$ time and $o(n\log\sigma)$ bits. If correct, this makes compressed suffix trees buildable for very large genomic collections in almost no extra memory.

What carries the argument

The machinery has two halves. First, LCP pairs and suffix-tree intervals are enumerated by traversing BWT intervals: from a range $[L,R]$ of a string $W$, the operation `getIntervals` uses a wavelet matrix to list, in $O(\log\sigma)$ time each, the new ranges of left-extensions $cW$. Right-maximal substrings—strings followed by at least two distinct characters, which are exactly the internal suffix-tree nodes—are visited via Weiner links, using a stack when the alphabet is small and a queue when it is large, with a threshold that keeps total working space $o(n\log\sigma)$. Second, the PLCP bitvector is assembled from irreducible LCP values using the facts that PLCP is almost increasing and that reducible values equal the previous value minus one; the topology is obtained by turning interval endpoints into open/close counters, blockwise, with block size $B=\epsilon\cdot n\log\sigma/\log\log n$.

What would settle it

Take a text with no repeated substrings, such as $T=\texttt{abcdef}$ plus its terminator, run the Section 8 topology construction, and count the open parentheses in the output: a correct BPS of the suffix tree has at least $n+1$ open parentheses (one per leaf plus the root), whereas an enumeration restricted to right-maximal substrings produces only the root's pair, so leaf-parent or depth operations on any leaf would fail.

Watch

Extended reading notes

Core claim

The central claim is that, given the word-packed Burrows-Wheeler transform of a text $T$ of length $n$ over alphabet $[1,\sigma]$ and any $0<\epsilon\le 1$, one can replace it with a compressed suffix tree in $O(n(\log\sigma + \epsilon^{-1}\log\log n))$ time and $\epsilon\cdot n\log\sigma + o(n)$ bits of working space, producing a structure of $n\log\sigma + 6n + o(n\log\sigma)$ bits that supports suffix-tree operations in $O(\operatorname{polylog} n)$ time. The construction assembles two enumeration procedures: one that outputs all pairs $(i,\mathrm{LCP}[i])$ and one that outputs all suffix-tree intervals, both in $O(n\log\sigma)$ time using $o(n\log\sigma)$ bits. Those enumerations feed blockwise computations of the PLCP bitvector and the balanced-parentheses topology, with $\epsilon$ controlling the space-time trade-off. The same traversal ideas give an $O(n\log\sigma)$-time, $o(n\log\sigma)$-space algorithm for merging the BWTs of two collections, and an implementation on DNA data uses about $n$ bits on top of a packed BWT while processing about 2.92 megabases per second.

Load-bearing premise

The topology construction assumes that enumerating intervals of right-maximal substrings and converting each interval's endpoints into open/close counters yields the full balanced-parentheses suffix tree, without separately adding the $n$ singleton leaf intervals corresponding to text positions.

Editorial extensions

If this is right

  • The LCP array of a string collection can be induced from the BWT in $O(n\log\sigma)$ time using $o(n\log\sigma)$ bits, matching the best time bound while using less space.
  • For any $\epsilon$, the PLCP bitvector and the BPS topology can be produced in $\epsilon\cdot n\log\sigma + o(n)$ bits; setting $\epsilon$ small gives a near-linear-time, succinct-space construction.
  • A complete compressed suffix tree can replace the BWT in $n\log\sigma + 6n + o(n\log\sigma)$ bits, with all operations in $O(\operatorname{polylog} n)$ time.
  • Two BWTs can be merged into the BWT of their union in $O(n\log\sigma)$ time and $o(n\log\sigma)$ bits, which also induces the LCP array of the merged collection.
  • An implementation on DNA alphabets uses as little as $n$ bits on top of the packed input/output and processes data at about 2.92 megabases per second.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The blockwise counter technique suggests a direct external-memory adaptation: choose $B$ so that one block of counters fits in RAM, stream the interval enumeration, and build the topology of arbitrarily large texts within the same space bound.
  • The same Weiner-link enumeration could supply the child and sibling navigational tables of a compressed suffix tree, so a full CST beyond BPS and PLCP may be constructible within the same $o(n\log\sigma)$ space bounds.
  • The merge algorithm's leaf-pair navigation is naturally generalizable to a multi-collection merge by maintaining one interval pair per collection, yielding a multi-way BWT merge with the same time per character.
  • Because the space bound is tunable through $\epsilon$, an implementation could adapt the parameter to available RAM, trading a $\log\log n$ factor in time for space as low as $o(n\log\sigma)$.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The manuscript studies the construction of compressed suffix tree components directly from the Burrows–Wheeler transform. It proposes algorithms to enumerate LCP values and suffix-tree intervals in O(n log σ) time with o(n log σ) bits of working space, and then uses them to build the PLCP bitvector and a BPS representation of the suffix tree topology in O(n(log σ + ε^{-1} log log n)) time with ε·n log σ + o(n) bits of working space. These results are combined into Theorem 5, which claims a compressed suffix tree in n log σ + 6n + o(n log σ) bits of space. The paper also presents a BWT-merging algorithm for string collections and reports an implementation (bwt2lcp, merge) on DNA data. The central claim is that this is the first succinct-space construction of all compressed suffix tree components from the BWT.

Significance. If the results were fully established, the LCP and PLCP constructions would improve the state of the art by replacing O(n)-bit working-space algorithms with o(n log σ)-bit algorithms, and the BWT-merge algorithm would improve the space of earlier work by Belazzougui et al. The paper is detailed, with careful complexity accounting in Sections 5 and 7, no fitted parameters, and reproducible experimental comparisons. However, the BPS construction in Section 8 omits the n leaf intervals, so Lemma 7 and Theorem 5 do not actually produce the claimed suffix tree topology as written. This is a local but load-bearing gap; the rest of the paper appears sound and the gap is likely fixable.

major comments (2)
  1. [Section 8, Lemmas 4 and 7] The topology construction increments Open[l] and Close[r] only for intervals returned by Lemma 4, which is explicitly restricted to the suffix array intervals of right-maximal text substrings. These are the internal suffix tree nodes. In the Sadakane BPS representation used by Theorem 5, each leaf with SA interval [i,i] must also contribute an opening parenthesis at position i and a closing parenthesis at position i, but such singleton leaf intervals are not right-maximal in general and are never enumerated by Lemma 4. The resulting parenthesis sequence therefore has at most 2·(#internal nodes) ≤ 2n bits instead of the roughly 4n bits of a suffix tree BPS, and leaf-oriented operations such as locating a leaf by select on '(' cannot work. Concretely, for T='ab#', Lemma 4 returns only the root interval [1,3], so the procedure outputs the sequence '()' rather than a BPS with three leaves. This is a correctness gap in Lemma 7 and in Theorem 5; a fix requires enumerating all leaf intervals [i,i] or adding them in a separate pass before the counter phase.
  2. [Section 8, final paragraph] The proof of Theorem 5 states that augmenting the BWT into a CSA can be done in O(n log σ) time and n + o(n) bits of working space. This is not reconciled with Theorem 5's stated working-space bound of ε·n log σ + o(n) bits on top of input and output: for σ = O(1) and small ε, n + o(n) exceeds the allowed amount. If the n-bit structures for suffix array sampling are intended to be placed in the output space (as is done in Lemma 1), that reuse must be stated explicitly; otherwise the space accounting for Theorem 5 is incomplete.
minor comments (5)
  1. [Section 8, final paragraph] The sentence 'Combining this with Lemmas 1, 6, and 5' appears to contain an incorrect lemma reference; Lemma 5 is the reducible-PLCP lemma, and the BPS construction is Lemma 7. It should likely read 'Lemmas 1, 6, and 7'.
  2. [Lemmas 6 and 7] The word 'optput' appears twice in the statements of Lemmas 6 and 7 and should be 'output'.
  3. [Section 5, proof of Lemma 3] In the complexity analysis of Algorithm 2, the text says that 'in Line 13 we output R−L−2 LCP values', but the loop in Algorithm 2 outputs LCP[L+1..R], which is R−L values; the formula should be corrected.
  4. [Section 3] The statement that 'explicit suffix tree nodes correspond to right-maximal substrings' is true only for internal nodes, since leaves are explicit nodes but not right-maximal. This terminology ambiguity is directly related to the Section 8 gap and should be clarified throughout the paper.
  5. [Section 7] The phrase 'using the FL function on the BWT' appears to refer to the LF mapping used to walk suffixes in text order; the nonstandard name 'FL' should be corrected or defined.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular dependency: the construction derives CST components from the BWT via externally cited enumeration theorems, and the only residual concern is a non-circular correctness gap about leaf intervals in Section 8.

full rationale

The derivation chain is input-driven rather than self-referential. Theorem 3 builds the LCP array from the BWT via Lemma 2, whose two branches use Belazzougui's Weiner-link enumeration (Theorem 1, externally cited) and Beller et al.'s interval queue (Theorem 2, externally cited), with correctness and completeness proved in Lemma 3. Lemma 4 reuses the same external enumeration machinery to list right-maximal suffix-array intervals, and Section 7's PLCP construction relies on the irreducible-LCP lemmas of Manzini and Kärkkäinen et al. (Lemma 5 and Theorem 4), with no fitted parameters or output quantities defined in terms of the claimed result. Section 8's BPS construction is an algorithmic adaptation of Belazzougui's counter scheme, and Theorem 5 merely assembles the PLCP bitvector, BPS topology, and CSA from the previously constructed pieces. The only self-citation is to the authors' CPM 2019 preliminary version for Contributions (1) and (3), but the current paper reproduces the proofs, so that citation is not load-bearing. A possible weakness noted by a reader is that Lemma 4 enumerates only right-maximal (internal-node) intervals, while the Sadakane BPS topology also requires the n singleton leaf intervals; the paper does not explicitly add them in Section 8. That is a potential correctness/completeness gap in the topology construction, not a circular reduction, because the missing leaves are not hidden inside the inputs by definition. Accordingly, no circularity step is identified and the circularity score is 0.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

No fitted parameters; ε is a user-specified trade-off. The substantive inputs are prior theorems from the literature and standard string-algorithm facts. The ad hoc assumption about the BPS construction being buildable from internal-node intervals alone is the main unsupported premise and appears false unless leaf intervals are added.

assumptions (8)
  • domain assumption Belazzougui's Weiner-link enumeration of right-maximal substrings runs in O(n log σ) time and O(σ² log² n) bits (Theorem 1).
    Used in Sections 3 and 5 as the small-alphabet building block; correctness is taken from Belazzougui's STOC 2014 paper.
  • domain assumption Beller et al.'s LCP enumeration runs in O(n log σ) time and O(n) bits (Theorem 2).
    Used in Sections 4 and 5 as the large-alphabet building block; the paper reformulates it but does not reprove its core properties.
  • domain assumption A word-packed string can be converted to a wavelet matrix in O(n log σ) time using n extra bits (Lemma 1, Claude et al.).
    Invoked in Theorems 3, 5, and 6 to turn the packed input BWT into a wavelet matrix for rank/select operations.
  • domain assumption The sum of all irreducible LCP values is at most 2n log n (Theorem 4, Kärkkäinen et al.).
    Used in Section 7 to bound the size of LARGE_LCP and the number of large irreducible LCP values.
  • domain assumption A reducible PLCP value equals the previous PLCP value minus 1 (Lemma 5, Manzini 2004).
    Used in Section 7 to fill in reducible PLCP bits from the nearest irreducible value.
  • domain assumption Wavelet tree data structure supports rank, rangeDistinct, getIntervals, and backward search in O(log σ) time per operation.
    Computational model throughout; the paper assumes the standard wavelet matrix interface without re-deriving it.
  • domain assumption The number of explicit Weiner links in a suffix tree is linear, even including implicit Weiner links.
    Used in Sections 3 and 5 to bound total work of the enumeration; cited to Belazzougui-Navarro and Belazzougui.
  • ad hoc to paper The BPS topology can be built by incrementing Open/Close counters only for intervals of right-maximal substrings, with no explicit leaf intervals.
    This unstated premise is the main gap: Lemma 4 enumerates only right-maximal intervals, but a complete suffix tree topology requires the n leaf intervals as well. The paper neither adds them nor justifies their omission.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Space-Efficient Construction of Compressed Suffix Trees." pith.science (2026). https://pith.science/paper/FL2SCFJW

@misc{pith2026190804686,
  author       = {Pith},
  title        = {Pith review of: Space-Efficient Construction of Compressed Suffix Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FL2SCFJW}},
  note         = {Machine review of arXiv:1908.04686}
}
abstract

We show how to build several data structures of central importance to string processing, taking as input the Burrows-Wheeler transform (BWT) and using small extra working space. Let $n$ be the text length and $\sigma$ be the alphabet size. We first provide two algorithms that enumerate all LCP values and suffix tree intervals in $O(n\log\sigma)$ time using just $o(n\log\sigma)$ bits of working space on top of the input BWT. Using these algorithms as building blocks, for any parameter $0 < \epsilon \leq 1$ we show how to build the PLCP bitvector and the balanced parentheses representation of the suffix tree topology in $O\left(n(\log\sigma + \epsilon^{-1}\cdot \log\log n)\right)$ time using at most $n\log\sigma \cdot(\epsilon + o(1))$ bits of working space on top of the input BWT and the output. In particular, this implies that we can build a compressed suffix tree from the BWT using just succinct working space (i.e. $o(n\log\sigma)$ bits) and any time in $\Theta(n\log\sigma) + \omega(n\log\log n)$. This improves the previous most space-efficient algorithms, which worked in $O(n)$ bits and $O(n\log n)$ time. We also consider the problem of merging BWTs of string collections, and provide a solution running in $O(n\log\sigma)$ time and using just $o(n\log\sigma)$ bits of working space. An efficient implementation of our LCP construction and BWT merge algorithms use (in RAM) as few as $n$ bits on top of a packed representation of the input/output and process data as fast as $2.92$ megabases per second.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 44 canonical work pages

  1. [1]

    Bauer, A.J

    M.J. Bauer, A.J. Cox, and G. Rosone. Lightweight algorit hms for constructing and inverting the BWT of string collections. Theor. Comput. Sci. , 483(0):134– 148, 2013

    work page 2013

  2. [2]

    Belazzougui

    D. Belazzougui. Linear time construction of compressed text indices in compact space. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC ’14, pages 148–193, New York, NY, USA, 2014. ACM

    work page 2014

  3. [3]

    Linear-time string indexing and analysis in small space

    D. Belazzougui, F. Cunial, J. K¨ arkk¨ ainen, and V. M¨ akinen. Linear-time string indexing and analysis in small space. arXiv preprint arXiv:1609.06378 , 2016

    work page Pith review arXiv 2016

  4. [4]

    Belazzougui and G

    D. Belazzougui and G. Navarro. Alphabet-independent co mpressed text indexing. TALG, 10(4):23, 2014

    work page 2014

  5. [5]

    Beller, S

    T. Beller, S. Gog, E. Ohlebusch, and T. Schnattinger. Com puting the longest common prefix array based on the Burrows–Wheeler transform. J. Discrete Algorithms, 18:22–31, 2013

    work page 2013

  6. [6]

    Beller, M

    T. Beller, M. Zwerger, S. Gog, and E. Ohlebusch. Space-Effi cient Construction of the Burrows-Wheeler Transform. In String Processing and Information Retrieval, pages 5–16, Cham, 2013. Springer International Publishin g

    work page 2013

  7. [7]

    Benoit, E

    D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman, a nd S. S. Rao. Representing trees of higher degree. Algorithmica, 43(4):275–292, 2005

    work page 2005

  8. [8]

    Bonizzoni, G

    P. Bonizzoni, G. Della Vedova, S. Nicosia, Y. Pirola, M. P revitali, and R. Rizzi. Divide and conquer computation of the multi-string BWT and L CP array. In CiE, LNCS, pages 107–117. Springer, 2018. 31

    work page 2018

Show all 45 references
  1. [9]

    Burrows and D.J

    M. Burrows and D.J. Wheeler. A Block Sorting data Compres sion Algorithm. Technical report, DEC Systems Research Center, 1994

    1994

  2. [10]

    Claude, G

    F. Claude, G. Navarro, and A. Ord´ onez. The wavelet matr ix: An efficient wavelet tree for large alphabets. Information Systems , 47:15–32, 2015

    2015

  3. [11]

    A.J. Cox, F. Garofalo, G. Rosone, and M. Sciortino. Ligh tweight LCP construction for very large collections of strings. J. Discrete Algorithms , 37:17– 33, 2016

    2016

  4. [12]

    Egidi, F.A

    L. Egidi, F.A. Louza, G. Manzini, and G.P. Telles. Exter nal memory BWT and LCP computation for sequence collections with application s. Algorithms Mol. Biol., 14(1):6, 2019

    2019

  5. [13]

    Egidi and G

    L. Egidi and G. Manzini. Lightweight BWT and LCP merging via the Gap algorithm. In SPIRE, LNCS, pages 176–190. Springer, 2017

    2017

  6. [14]

    Ferragina and G

    P. Ferragina and G. Manzini. Opportunistic data struct ures with applications. In FOCS, pages 390–398. IEEE, 2000

    2000

  7. [15]

    Fuentes-Seplveda, G

    J. Fuentes-Seplveda, G. Navarro, and Y. Nekrich. Space -efficient computation of the burrows-wheeler transform. In 2019 Data Compression Conference (DCC), pages 132–141, 2019

    2019

  8. [16]

    N. Gonzalo. Wavelet trees for all. J. Discrete Algorithms , 25:2 – 20, 2014

    2014

  9. [17]

    Grossi and J

    R. Grossi and J. S. Vitter. Compressed suffix arrays and su ffix trees with applications to text indexing and string matching. SIAM J. Comput. , 35(2):378–407, 2005

    2005

  10. [18]

    Guerrini and G

    V. Guerrini and G. Rosone. Lightweight Metagenomic Cla ssification via eBWT. In Algorithms for Computational Biology , volume 11488 LNBI, pages 112–124. Springer International Publishing, 2019

    2019

  11. [19]

    Holt and L

    J. Holt and L. McMillan. Constructing Burrows-Wheeler transforms of large string collections via merging. In ACM-BCB, pages 464–471. ACM, 2014

    2014

  12. [20]

    Holt and L

    J. Holt and L. McMillan. Merging of multi-string BWTs wi th applications. Bioinformatics, 30(24):3524–3531, 2014

    2014

  13. [21]

    W.-K. Hon, K. Sadakane, and W.-K. Sung. Breaking a time- and-space barrier in constructing full-text indices. SIAM J. Comput. , 38(6):2162–2178, 2009

    2009

  14. [22]

    K¨ arkk¨ ainen

    J. K¨ arkk¨ ainen. Fast BWT in small space by blockwise su ffix sorting. Theor. Comput. Sci. , 387(3):249–257, 2007

    2007

  15. [23]

    K¨ arkk¨ ainen, G

    J. K¨ arkk¨ ainen, G. Manzini, and S. J. Puglisi. Permuted longest-common-prefix array. In Combinatorial Pattern Matching , pages 181–192, Berlin, Heidelberg,

  16. [24]

    Kasai, G

    T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park. Lin ear-time longest-common-prefix computation in suffix arrays and its ap plications. In Combinatorial Pattern Matching , pages 181–192, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg. 32

    2001

  17. [25]

    String synchroniz ing sets: Sublinear- time bwt construction and optimal lce data structure

    Dominik Kempa and Tomasz Kociumaka. String synchroniz ing sets: Sublinear- time bwt construction and optimal lce data structure. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , STOC 2019, pages 756–767, New York, NY, USA, 2019. ACM

    2019

  18. [26]

    Louza, G.P

    F.A. Louza, G.P. Telles, S. Hoffmann, and C.D.A. Ciferri. Generalized enhanced suffix array construction in external memory. Algorithms Mol. Biol. , 12(1):26, 2017

    2017

  19. [27]

    Manber and G

    U. Manber and G. Myers. Suffix arrays: A new method for on-l ine string searches. SIAM Journal on Computing , 22(5):935–948, 1993

    1993

  20. [28]

    Mantaci, A

    S. Mantaci, A. Restivo, G. Rosone, and M. Sciortino. An e xtension of the Burrows-Wheeler Transform. Theor. Comput. Sci. , 387(3):298–312, 2007

    2007

  21. [29]

    Two space saving tricks for linear ti me lcp array computation

    Giovanni Manzini. Two space saving tricks for linear ti me lcp array computation. In Torben Hagerup and Jyrki Katajainen, edito rs, Algorithm Theory - SWAT 2004 , pages 372–383, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg

    2004

  22. [30]

    J. I. Munro, G. Navarro, and Y. Nekrich. Space-efficient c onstruction of compressed indexes in deterministic linear time. In SODA, pages 408–424. SIAM, 2017

    2017

  23. [31]

    J. I. Munro and V. Raman. Succinct representation of bal anced parentheses, static trees and planar graphs. In Proceedings of the 38th Annual Symposium on Foundations of Computer Science , FOCS ’97, pages 118–, Washington, DC, USA, 1997. IEEE Computer Society

    1997

  24. [32]

    Compact Data Structures: A Practical Approach

    Gonzalo Navarro. Compact Data Structures: A Practical Approach . Cambridge University Press, New York, NY, USA, 1st edition, 2016

    2016

  25. [33]

    Optimal dynamic seq uence representations

    Gonzalo Navarro and Yakov Nekrich. Optimal dynamic seq uence representations. SIAM Journal on Computing , 43(5):1781–1806, 2014

    2014

  26. [34]

    Ohlebusch, J

    E. Ohlebusch, J. Fischer, and S. Gog. Cst++. In String Processing and Information Retrieval, pages 322–333, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg

    2010

  27. [35]

    Policriti, N

    A. Policriti, N. Gigante, and N. Prezza. Average Linear Time and Compressed Space Construction of the Burrows-Wheeler Transform. In Language and Automata Theory and Applications , pages 587–598, Cham, 2015. Springer International Publishing

    2015

  28. [36]

    Prezza, N

    N. Prezza, N. Pisanti, M. Sciortino, and G. Rosone. Dete cting Mutations by eBWT. In WABI 2018, volume 113 of LIPIcs, pages 3:1–3:15, 2018

    2018

  29. [37]

    Prezza, N

    N. Prezza, N. Pisanti, M. Sciortino, and G. Rosone. SNPs detection by eBWT positional clustering. Algorithms Mol. Biol. , 14(1):3, 2019

    2019

  30. [38]

    Prezza and G

    N. Prezza and G. Rosone. Space-Efficient Computation of t he LCP Array from the Burrows-Wheeler Transform. In 30th Annual Symposium on Combinatorial 33 Pattern Matching (CPM 2019) , volume 128 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 7:1–7:18, Dagstuh...

    2019

  31. [39]

    Puglisi and A

    S.J. Puglisi and A. Turpin. Space-time tradeoffs for long est-common-prefix array computation. In ISAAC, volume 5369 of LNCS, pages 124–135. Springer, 2008

    2008

  32. [40]

    Sadakane

    K. Sadakane. Succinct representations of lcp informat ion and improvements in the compressed suffix arrays. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA ’02, pages 225–232, Philadelphia, PA, USA, 2002. Society for Industrial and App li...

    2002

  33. [41]

    Sadakane

    K. Sadakane. Compressed suffix trees with full functiona lity. Theor. Comp. Sys., 41(4):589–607, 2007

    2007

  34. [42]

    F. Shi. Suffix arrays for multiple strings: A method for on -line multiple string searches. In ASIAN, volume 1179 of LNCS, pages 11–22. Springer, 1996

    1996

  35. [43]

    Tustumi, Simon Gog, Guilherme P

    William H.A. Tustumi, Simon Gog, Guilherme P. Telles, a nd Felipe A. Louza. An improved algorithm for the all-pairs suffixprefix problem. Journal of Discrete Algorithms, 37:34 – 43, 2016

    2016

  36. [44]

    V¨ alim¨ aki, V

    N. V¨ alim¨ aki, V. M¨ akinen, W. Gerlach, and K. Dixit. Engineering a compressed suffix tree implementation. J. Exp. Algorithmics , 14:2:4.2–2:4.23, 2010. 34

    2010

  37. [2009]

    Springer Berlin Heidelberg

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.