Pith. sign in

REVIEW 2 major objections 4 minor 48 references

Compressed Dictionary Matching on Run-Length Encoded Strings

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read This paper shows that dictionary matching on run-length encoded strings can report all pattern occurrences in time near-linear in the number of runs, using space proportional to the patterns' runs.

desk verdict Nice techniques, but the central transition rule misses occurrences when text runs are longer than pattern edges; the main theorem is false as written. read the letter →

arxiv 2509.03265 v1 pith:LAWICUEL submitted 2025-09-03 cs.DS

Philip Bille , Inge Li G{o}rtz , Simon J. Puglisi , Simon R. Tarnow This is my paper · ORCID
classification cs.DS
keywords dictionarymatchingrun-lengthencodingAho-Corasickautomatoncompressedpatterncompacttrietruncatematchreportingcoloredancestorthresholdpredecessorsearch
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

Dictionary matching asks for every occurrence of any pattern from a set in a text. When both patterns and text contain long runs of identical characters, run-length encoding makes the input much smaller than the uncompressed strings, and the question is whether matching can be solved in time tied to that compressed size. The paper answers yes: from the run-length encodings alone, all occurrences can be reported in $O((\overline{m}+\overline{n})\log\log m+\mathrm{occ})$ expected time and $O(\overline{m})$ space, where $\overline{m}$ and $\overline{n}$ are the run counts of the patterns and text and $\mathrm{occ}$ is the number of matches. This is the first non-trivial algorithm for compressed dictionary matching on run-length encoded strings, and since reading the input is unavoidable the time bound is optimal within a $\log\log m$ factor. The construction compresses the classic Aho-Corasick automaton so that the text is processed one run at a time, with a new truncate-match reporting data structure handling occurrences that end inside a run.

What carries the argument

The load-bearing object is the run-length encoded trie $T_{\mathrm{RLE}}$, the trie over the pattern set in which every maximal run $\alpha^x$ is compressed to a single edge label. The paper simulates the Aho-Corasick automaton on this trie by redefining failure links to skip to the longest suffix with at least one fewer run, grouping nodes that share a suffix except for the length of their first run, and giving each group a predecessor dictionary keyed by first-run length. Occurrences ending inside the current run of the text are delegated to the truncate match reporting problem, which the paper reduces to colored ancestor threshold reporting: given a node, a color, and a weight threshold, report all ancestors carrying that color with weight at most the threshold. The whole construction depends on a new reduction that sorts run-length encoded strings by sorting their run-pair encodings and then converts the compact trie of run-pair strings into the compact trie of the original strings in linear time.

What would settle it

Build a pattern set where several children of one trie node share the same first run character and a shorter child edge has a nonempty continuation, run the paper's transformation, and compare the resulting compact trie with the trie built directly from the uncompressed strings; any mismatch in node depths, edge labels, or child order falsifies the central claim. A looser empirical falsifier is a timing test on inputs with very long runs: if the algorithm's total time ever scales with the uncompressed length rather than with $\overline{m}+\overline{n}$ plus occurrences, the claimed bound fails.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: given the run-length encoding of a pattern set $\mathcal{P}$ (with $\overline{m}$ runs) and a text $S$ (with $\overline{n}$ runs), dictionary matching can be solved in $O((\overline{m}+\overline{n})\log\log m+\mathrm{occ})$ expected time and $O(\overline{m})$ space. The paper achieves this by building the run-length encoded trie $T_{\mathrm{RLE}}$ of the patterns, in which each run $\alpha^x$ is one edge label, and simulating the Aho-Corasick automaton directly on this compressed trie. Failure links are redefined to point to suffixes with strictly fewer runs, nodes that differ only by the length of their first run are grouped and navigated with predecessor search, and occurrences ending inside the current text run are reported through the new truncate match reporting problem, reduced to colored ancestor threshold reporting on the compact trie of reversed truncated patterns. A deterministic counterpart (Theorem 2) reaches $O((\overline{m}+\overline{n})\log\log(\overline{m}+\overline{n})+\mathrm{occ})$ time and $O(\overline{n}+\overline{m})$ space after reducing the alphabet by sorting the runs of both patterns and text.

Load-bearing premise

Everything rests on the linear-time transformation that turns the compact trie over run-pair encoded strings into the compact trie over the original strings. That transformation must correctly handle every configuration of children sharing the same first run character, especially a shorter child edge whose label continues; if a case is missed, the compressed preprocessing and the final time bounds collapse.

Editorial extensions

If this is right

  • Dictionary matching on run-length encoded text and patterns can be solved in time near-linear in the number of runs, so inputs with very long repeated-character runs no longer require work proportional to the uncompressed length.
  • The classic Aho-Corasick automaton can be simulated in $O(\overline{m})$ space without materializing every pattern prefix, by grouping automaton states and using predecessor search.
  • Occurrences ending inside the last processed run are handled by the new truncate-match structure, which reduces that task to colored ancestor threshold reporting on a compact trie.
  • A deterministic variant achieves nearly the same bounds in worst-case time, at the cost of an alphabet-reduction sorting step that uses $O(\overline{n})$ additional space.
  • Since any correct algorithm must read its input, the randomized time bound is optimal up to the $\log\log m$ factor.

Reading between the lines

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

  • Editorial extension: grouping RLE-trie nodes by suffix-and-first-run-length is a reusable compression idea that could be applied to other automaton-based string problems, such as multiple-pattern longest common prefix queries or streaming matching on highly repetitive text.
  • Editorial extension: the truncate match reporting primitive isolates the partial-run boundary where ordinary automaton states cannot represent the overlap, so it may transfer to matching with wildcards, gaps, or approximate matches inside a run.
  • Editorial extension: a natural empirical check is whether the $\log\log m$ predecessor term or the compact-trie transformation dominates in practice on highly repetitive corpora; the theory predicts both should scale with run counts, not uncompressed lengths.
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 / 4 minor

Summary. The paper studies compressed dictionary matching for run-length encoded (RLE) strings, aiming to report all occurrences of a pattern set P in a text S without decompressing either string. It proposes an algorithm based on a run-length encoded trie (TRLE) that simulates the Aho-Corasick automaton one run at a time, together with a new "truncate match reporting" data structure. The main claimed result, Theorem 1, is an O((m̄+n̄) log log m + occ) expected-time and O(m̄)-space algorithm, with a deterministic variant in Theorem 2. The paper also develops compressed sorting of RLE strings and a reduction to colored ancestor threshold reporting.

Significance. If correct, the result would be the first non-trivial algorithm for compressed dictionary matching on run-length encoded strings, and the proposed TRLE representation and truncate match reporting techniques could be of independent interest. The paper demonstrates technical sophistication in combining known data structures (perfect hashing, y-fast tries, path minima, level ancestors, first color ancestor) into a compressed AC automaton. However, the central query transition is incorrect: it does not handle text runs that are longer than the corresponding pattern run, a case that arises in ordinary string matching. Since the counterexample below invalidates the main theorems, the claimed results are not established.

major comments (2)
  1. [Section 5, Step 2 (and Section 6, Step 2)] The transition rule only follows an edge when the current text run label α^y exactly equals an edge label in the dictionary D_v (or in the group dictionary D_G). In ordinary run-length matching, a pattern run α^x should be allowed to match a text run α^y when x ≤ y, with the occurrence ending inside the text run. Consider P = {a^3 b} and S = a^4 b. The occurrence at position 1 is reported by the uncompressed Aho-Corasick algorithm, but the proposed algorithm processes run a^4 from the root: since a^4 is not an edge label from the root, the state remains the root; then run b^1 is processed, again with no edge, and no occurrence is reported. The correctness proof's induction fails exactly when the longest suffix of S'α^y is a proper prefix of α^y, because the proof writes the suffix as s_{u'} α^y, which is impossible when the suffix ends inside the run. The truncate match reporting step cannot compensate because it queries with i_v, which is already wrong when the state is root. This counterexample also invalidates Theorem 2, since the deterministic algorithm uses the same transition rule.
  2. [Section 6, Step 2 and correctness proof] The same issue appears in the full algorithm. The correctness proof again assumes that the longest suffix of S'α^y decomposes as s_{u'} α^y, requiring the suffix to include the full text run α^y. When the text run is longer than every available pattern run prefix, the correct automaton state should be a node whose string is a proper prefix of α^y (e.g., a^3 when processing a^4), but the algorithm never considers such a node because it only takes edges labeled exactly α^y. Consequently, the invariant that s_v is the longest suffix of S' is violated after the first run of the counterexample, and the induction step in the proof of Section 6 breaks for the same reason as in Section 5.
minor comments (4)
  1. [Section 6, Step 2] The paper defines Z_v as the length of the first run of s_v, but never defines Z_v for the root node, whose string is the empty string. The query 'if D_G[α^y] has a predecessor u to Z_v' requires a value for the root; if the intended convention is Z_root = 0, it should be stated explicitly.
  2. [Abstract and Section 5, Lemma 7] The notation n and m is used inconsistently: the abstract uses m and n for the total uncompressed lengths and \bar{m}, \bar{n} for the number of runs, but Lemma 7 states 'consisting of m and n runs' while also referring to 'a string S of length n'. This overloading makes the time bounds ambiguous and should be corrected throughout.
  3. [Section 3, Lemma 3] The transformation from the compact trie of run-pair strings to the compact trie of uncompressed strings is described only for two adjacent children in the loop. The case of three or more children sharing the same first run character is not fully spelled out; a more detailed case analysis or a worked example would improve clarity, since Corollary 1 and Lemma 4 depend on this transformation.
  4. [References] References [33] and [34] appear to be the same paper (both are listed as 'Approximating LZ77 via small-space multiple-pattern matching' by Fischer et al. in ESA 2015); one duplicate should be removed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithm's bounds derive from standard external data structures and new reductions, with no fitted parameter, self-citation chain, or prediction-by-construction.

full rationale

The paper's central claim (Theorem 1) is an algorithmic time/space bound for compressed dictionary matching on run-length encoded strings. The derivation is self-contained in the relevant sense: it builds a run-length encoded trie TRLE, constructs it via a sorting reduction (Corollary 1 and Lemma 4) whose complexity is justified by the external sorting result of Andersson and Nilsson [14], and handles output reporting through a new truncate-match-reporting problem solved with standard tree data structures (first color ancestor, path minima, level ancestor, perfect hashing, y-fast tries). No parameter is fitted to any subset of the target data and then renamed a prediction. The only occurrences of the present authors' prior work in the reference list (e.g., [21], [22]) appear in the introduction as examples of applications or as background citations, not as load-bearing justification for the main theorem or for any uniqueness or optimality claim. The statement that the bound is optimal within a log log m factor is justified by the unremarkable fact that any solution must read the input, not by a self-cited impossibility theorem. The paper does import known data-structure primitives, but those are independently established external results with stated assumptions; importing them is standard evidence, not circularity. The skeptical counterexample concerning text runs longer than pattern runs would, if valid, be a correctness defect in the transition rule and correctness proof of Sections 5 and 6, not a circularity: the algorithm's claimed behavior does not reduce by definition to its inputs. Since no specific reduction of a derived claim to its own inputs, no fitted input called a prediction, and no load-bearing self-citation chain was found, the appropriate circularity score is 0.

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

The central claim rests on standard data-structure primitives (perfect hashing, y-fast tries, path minima, level ancestors, first color ancestor, sorting) and the word-RAM model. No free parameters are fitted and no new physical or computational entities are postulated beyond the new data structures. The proof of Lemma 3's transformation is the most intricate unformalized step.

assumptions (7)
  • standard math Word-RAM model with logarithmic word length and read-only input.
    Stated before Theorem 1; space counts working words, not the input strings.
  • standard math FKS perfect hashing supports constant-time membership queries with O(n) space.
    Used for membership dictionaries, Section 2 and throughout.
  • standard math Willard's y-fast trie supports predecessor queries in O(log log u) time with O(n) space.
    Used in Lemma 1 and in the grouped failure-link navigation.
  • standard math Andersson-Nilsson string sorting achieves O(N + k log log k) time for sorting strings.
    Used in Corollary 1 to sort RLE strings and build compact tries.
  • standard math First color ancestor data structures answer nearest colored ancestor in O(log log n) time with linear space.
    Used in Lemma 5 for colored ancestor threshold reporting; cites [3,28,32,44].
  • standard math Path minima and level ancestor data structures on trees use linear space and constant query time.
    Used inside the colored ancestor threshold reporting query in Lemma 5.
  • standard math Han's deterministic sorting and Ruzic's deterministic perfect hashing exist with the stated bounds.
    Used in Section 7 to build deterministic predecessor structures.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Compressed Dictionary Matching on Run-Length Encoded Strings." pith.science (2026). https://pith.science/paper/LAWICUEL

@misc{pith2026250903265,
  author       = {Pith},
  title        = {Pith review of: Compressed Dictionary Matching on Run-Length Encoded Strings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LAWICUEL}},
  note         = {Machine review of arXiv:2509.03265}
}
abstract

Given a set of pattern strings $\mathcal{P}=\{P_1, P_2,\ldots P_k\}$ and a text string $S$, the classic dictionary matching problem is to report all occurrences of each pattern in $S$. We study the dictionary problem in the compressed setting, where the pattern strings and the text string are compressed using run-length encoding, and the goal is to solve the problem without decompression and achieve efficient time and space in the size of the compressed strings. Let $m$ and $n$ be the total length of the patterns $\mathcal{P}$ and the length of the text string $S$, respectively, and let $\overline{m}$ and $\overline{n}$ be the total number of runs in the run-length encoding of the patterns in $\mathcal{P}$ and $S$, respectively. Our main result is an algorithm that achieves $O( (\overline{m} + \overline{n})\log \log m + \mathrm{occ})$ expected time, and $O(\overline{m})$ space, where $\mathrm{occ}$ is the total number of occurrences of patterns in $S$. This is the first non-trivial solution to the problem. Since any solution must read the input, our time bound is optimal within an $\log \log m$ factor. We introduce several new techniques to achieve our bounds, including a new compressed representation of the classic Aho-Corasick automaton and a new efficient string index that supports fast queries in run-length encoded strings.

Figures

Figures reproduced from arXiv: 2509.03265 by the authors.

Figure 1
Figure 1. The strings P1 and P2 where P ′ 1 and P ′ 2 is the truncated string of P1 and P2, respectively. If P ′ 1 is a suffix of P ′ 2 then P1 truncate matches P2 since the length of the last run in P1 is no longer than in P2 and is the same character. Andersson and Nilsson [14] showed how to sort strings in t(k, m, σ) = O(m + k log log k) expected time and s(k, m, σ) = O(m) space. We obtain the following result by plugging … view at source ↗
Figure 2
Figure 2. The structures of lemma 5 and lemma 6 for the strings [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. The structure of the simple solution for the 6 patterns [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The structure of the full solution for the 6 patterns [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 48 canonical work pages

  1. [1]

    Aho and Margaret J

    Alfred V. Aho and Margaret J. Corasick. Efficient string matching: An aid to bibliographic search. Commun. ACM, 18(6):333–340, 1975

    work page 1975

  2. [2]

    Improved algorithms for finding level ancestors in dynamic trees

    Stephen Alstrup and Jacob Holm. Improved algorithms for finding level ancestors in dynamic trees. In Proc. 27th ICALP, pages 73–84, 2000

    work page 2000

  3. [3]

    Marked ancestor problems

    Stephen Alstrup, Thore Husfeldt, and Theis Rauhe. Marked ancestor problems. In Proc. 39th FOCS, pages 534–544, 1998

    work page 1998

  4. [4]

    Efficient two-dimensional compressed matching

    Amihood Amir and Gary Benson. Efficient two-dimensional compressed matching. In Proc. 2nd DCC, pages 279–288, 1992

    work page 1992

  5. [5]

    Optimal two-dimensional compressed matching

    Amihood Amir, Gary Benson, and Martin Farach. Optimal two-dimensional compressed matching. J. Algorithms, 24(2):354–379, 1997

    work page 1997

  6. [6]

    Adaptive dictionary matching

    Amihood Amir and Martin Farach. Adaptive dictionary matching. In Proc. 32nd FOCS , pages 760–766, 1991

    work page 1991

  7. [7]

    Dynamic dictionary matching

    Amihood Amir, Martin Farach, Zvi Galil, Raffaele Giancarlo, and Kunsoo Park. Dynamic dictionary matching. J. Comput. Syst. Sci. , 49(2):208–222, 1994

    work page 1994

  8. [8]

    Idury, Johannes A

    Amihood Amir, Martin Farach, Ramana M. Idury, Johannes A. La Poutr´ e, and Alejandro A. Sch¨ affer. Improved dynamic dictionary matching.Inf. Comput., 119(2):258–282, 1995

    work page 1995

Show all 48 references
  1. [9]

    Riva Shalom

    Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom. Mind the gap! - online dictionary matching with one gap. Algorithmica, 81(6):2123–2157, 2019

    2019

  2. [10]

    Landau, and Dina Sokol

    Amihood Amir, Gad M. Landau, and Dina Sokol. Inplace run-length 2d compressed search. Theor. Comput. Sci., 290(3):1361–1383, 2003

    2003

  3. [11]

    Riva Shalom

    Amihood Amir, Avivit Levy, Ely Porat, and B. Riva Shalom. Dictionary matching with one gap. In Proc. 25th CPM, pages 11–20, 2014

    2014

  4. [12]

    Riva Shalom

    Amihood Amir, Avivit Levy, Ely Porat, and B. Riva Shalom. Dictionary matching with a few gaps. Theor. Comput. Sci. , 589:34–46, 2015

    2015

  5. [13]

    Faster algorithms for string matching with k mismatches

    Amihood Amir, Moshe Lewenstein, and Ely Porat. Faster algorithms for string matching with k mismatches. J. Algorithms, 50(2):257–275, 2004

    2004

  6. [14]

    A new efficient radix sort

    Arne Andersson and Stefan Nilsson. A new efficient radix sort. In Proc. 35th FOCS, pages 714–721, 1994

    1994

  7. [15]

    Landau, and Steven Skiena

    Alberto Apostolico, Gad M. Landau, and Steven Skiena. Matching for run-length encoded strings. J. Complex., 15(1):4–16, 1999

    1999

  8. [16]

    Iliopoulos, Chang Liu, and Solon P

    Tanver Athar, Carl Barton, Widmer Bland, Jia Gao, Costas S. Iliopoulos, Chang Liu, and Solon P. Pissis. Fast circular dictionary-matching algorithm. Math. Struct. Comput. Sci. , 27(2):143–156, 2017

    2017

  9. [17]

    Which regular expression patterns are hard to match? In Proc

    Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard to match? In Proc. 57th FOCS, pages 457–466, 2016

    2016

  10. [18]

    Succinct dictionary matching with no slowdown

    Djamal Belazzougui. Succinct dictionary matching with no slowdown. In Proc. 21st CPM , pages 88–100, 2010. 14

    2010

  11. [19]

    Worst-case efficient single and multiple string matching on packed texts in the word-ram model

    Djamal Belazzougui. Worst-case efficient single and multiple string matching on packed texts in the word-ram model. J. Discrete Algorithms, 14:91–106, 2012

    2012

  12. [20]

    Finding level-ancestors in trees

    Omer Berkman and Uzi Vishkin. Finding level-ancestors in trees. J. Comput. Syst. Sci. , 48(2):214– 230, 1994

    1994

  13. [21]

    String matching with variable length gaps

    Philip Bille, Inge Li Gørtz, Hjalte Wedel Vildhøj, and David Kofoed Wind. String matching with variable length gaps. Theoret. Comput. Sci., 443:25–34, 2012

    2012

  14. [22]

    Regular expression matching with multi-strings and intervals

    Philip Bille and Mikkel Thorup. Regular expression matching with multi-strings and intervals. In Proc. 21st SODA, 2010

    2010

  15. [23]

    Chang and Eugene L

    William I. Chang and Eugene L. Lawler. Sublinear approximate string matching and biological applications. Algorithmica, 12(4):327–344, 1994

    1994

  16. [24]

    Computing on a free tree via complexity-preserving mappings

    Bernard Chazelle. Computing on a free tree via complexity-preserving mappings. Algorithmica, 2:337–361, 1987

    1987

  17. [25]

    Dictionary matching in a stream

    Rapha¨ el Clifford, Allyx Fontaine, Ely Porat, Benjamin Sach, and Tatiana Starikovskaya. Dictionary matching in a stream. In Proc. 23rd ESA, pages 361–372, 2015

    2015

  18. [26]

    Dictionary matching and indexing with errors and don’t cares

    Richard Cole, Lee-Ad Gottlieb, and Moshe Lewenstein. Dictionary matching and indexing with errors and don’t cares. In Proc. 36th STOC, pages 91–100, 2004

    2004

  19. [27]

    A string matching algorithm fast on the average

    Beate Commentz-Walter. A string matching algorithm fast on the average. In Hermann A. Maurer, editor, Proc. 6th ICALP, volume 71, pages 118–132, 1979

    1979

  20. [28]

    Paul F. Dietz. Fully persistent arrays (extended array). In Proc. 1st WADS, pages 67–74, 1989

    1989

  21. [29]

    Paul F. Dietz. Finding level-ancestors in dynamic trees. In Proc. 2nd WADS, pages 32–40, 1991

    1991

  22. [30]

    Eltabakh, Wing-Kai Hon, Rahul Shah, Walid G

    Mohamed Y. Eltabakh, Wing-Kai Hon, Rahul Shah, Walid G. Aref, and Jeffrey Scott Vitter. The sbc-tree: an index for run-length compressed sequences. In Proc. 11th EDBT, pages 523–534, 2008

    2008

  23. [31]

    Dynamic dictionary matching in external memory

    Paolo Ferragina and Fabrizio Luccio. Dynamic dictionary matching in external memory. Inf. Com- put., 146(2):85–99, 1998

    1998

  24. [32]

    Muthukrishnan

    Paolo Ferragina and S. Muthukrishnan. Efficient dynamic method-lookup for object oriented lan- guages (extended abstract). In Proc. 4th ESA, pages 107–120, 1996

    1996

  25. [33]

    Approximating LZ77 via small-space multiple-pattern matching

    Johannes Fischer, Travis Gagie, Pawel Gawrychowski, and Tomasz Kociumaka. Approximating LZ77 via small-space multiple-pattern matching. In Proc. 23rd ESA, pages 533–544, 2015

    2015

  26. [34]

    Approximating lz77 via small-space multiple-pattern matching

    Johannes Fischer, Travis Gagie, Pawe l Gawrychowski, and Tomasz Kociumaka. Approximating lz77 via small-space multiple-pattern matching. In Proc. 23rd ESA, pages 533–544, 2015

    2015

  27. [35]

    Fredman, J´ anos Koml´ os, and Endre Szemer´ edi

    Michael L. Fredman, J´ anos Koml´ os, and Endre Szemer´ edi. Storing a sparse table with O(1) worst case access time. In Proc. 23rd FOCS, pages 165–169, 1982

    1982

  28. [36]

    A framework for dynamic parameterized dictionary matching

    Arnab Ganguly, Wing-Kai Hon, and Rahul Shah. A framework for dynamic parameterized dictionary matching. In Proc. 15th SWAT, pages 10:1–10:14, 2016

    2016

  29. [37]

    Real-time streaming multi-pattern search for constant alphabet

    Shay Golan and Ely Porat. Real-time streaming multi-pattern search for constant alphabet. In Proc. 25th ESA, pages 41:1–41:15, 2017

    2017

  30. [38]

    Deterministic sorting in o( nloglogn) time and linear space

    Yijie Han. Deterministic sorting in o( nloglogn) time and linear space. J. Algorithms, 50(1):96–105, 2004

    2004

  31. [39]

    Thankachan, and Jeffrey Scott Vitter

    Wing-Kai Hon, Tsung-Han Ku, Rahul Shah, Sharma V. Thankachan, and Jeffrey Scott Vitter. Faster compressed dictionary matching. Theor. Comput. Sci. , 475:113–119, 2013

    2013

  32. [40]

    Com- pressed automata for dictionary matching

    Tomohiro I, Takaaki Nishimoto, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Com- pressed automata for dictionary matching. Theor. Comput. Sci. , 578:30–41, 2015. 15

    2015

  33. [41]

    Mul- tiple pattern matching in LZW compressed text

    Takuya Kida, Masayuki Takeda, Ayumi Shinohara, Masamichi Miyazaki, and Setsuo Arikawa. Mul- tiple pattern matching in LZW compressed text. In Proceedings of the 8th Data Compression Con- ference, pages 103–112, 1998

    1998

  34. [42]

    Knuth, James H

    Donald E. Knuth, James H. Morris Jr., and Vaughan R. Pratt. Fast pattern matching in strings. SIAM J. Comput. , 6(2):323–350, 1977

    1977

  35. [43]

    Succinct online dictionary matching with improved worst-case guarantees

    Tsvi Kopelowitz, Ely Porat, and Yaron Rozen. Succinct online dictionary matching with improved worst-case guarantees. In Proc. 27th CPM, pages 6:1–6:13, 2016

    2016

  36. [44]

    Muthukrishnan and Martin M¨ uller

    S. Muthukrishnan and Martin M¨ uller. Time and space efficient method-lookup for object-oriented programs (extended abstract). In Proc. 7th SODA, pages 42–51, 1996

    1996

  37. [45]

    A guided tour to approximate string matching

    Gonzalo Navarro. A guided tour to approximate string matching. ACM Comput. Surv., 33(1):31–88, 2001

    2001

  38. [46]

    Constructing efficient dictionaries in close to sorting time

    Milan Ruˇ zi´ c. Constructing efficient dictionaries in close to sorting time. InProc. 35th ICALP, pages 84–95, 2008

    2008

  39. [47]

    Computing the longest common subsequence of two run-length encoded strings

    Yoshifumi Sakai. Computing the longest common subsequence of two run-length encoded strings. In Proc. 23rd ISAAC, pages 197–206, 2012

    2012

  40. [48]

    Dan E. Willard. Log-logarithmic worst-case range queries are possible in space theta(n).Inf. Process. Lett., 17(2):81–84, 1983. 16

    1983

Pith tools

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