Every string admits a substring equation system representation of size O(χ(w)), providing the first such scheme for the repetitiveness measure χ.
Optimal suffix tree construction with large alphabets
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
fields
cs.DS 3representative citing papers
Dynamic LCS maintained under edits in amortized O(log^7 n) time whp, with Omega(log n / log log n) lower bound.
A Fiat-Naor-based inversion technique yields data structures for range searching, counting, and related queries on implicit sets f([N]) with ~O(N^{1-α/3}) space and ~O(N^α) query time for any α ∈ (0,1).
citing papers explorer
-
String Representation in Suffixient Set Size Space
Every string admits a substring equation system representation of size O(χ(w)), providing the first such scheme for the repetitiveness measure χ.
-
Dynamic Longest Common Substring in Polylogarithmic Time
Dynamic LCS maintained under edits in amortized O(log^7 n) time whp, with Omega(log n / log log n) lower bound.
-
A General Technique for Searching in Implicit Sets via Function Inversion
A Fiat-Naor-based inversion technique yields data structures for range searching, counting, and related queries on implicit sets f([N]) with ~O(N^{1-α/3}) space and ~O(N^α) query time for any α ∈ (0,1).