StringologyTimes

Papers for stringologist (2025)

• ACNS (1)(2025) [dblp]
• COCOON (2)(2025) [dblp]
• CPP(2025) [dblp]
• ICIC (26)(2025) [dblp]
• IJTCS-FAW(2025) [dblp]
• RECOMB(2025) [dblp]

• STOC(2025) [dblp]

• Acta Informatica(2025) [dblp]
• Algorithms(2025) [dblp]
• Algorithms Mol. Biol.(2025) [dblp]
• CoRR(2025) [dblp]
• Comput. J.(2025) [dblp]
• Eur. J. Comb.(2025) [dblp]
• Geo spatial Inf. Sci.(2025) [dblp]
• Inf. Comput.(2025) [dblp]
• Inf. Process. Lett.(2025) [dblp]
• Inf. Syst.(2025) [dblp]
• Int. J. Found. Comput. Sci.(2025) [dblp]
• J. Autom. Reason.(2025) [dblp]
• J. Heuristics(2025) [dblp]
• J. Syst. Softw.(2025) [dblp]
• Nat. Comput.(2025) [dblp]
• Pattern Anal. Appl.(2025) [dblp]
• SoftwareX(2025) [dblp]
• Theor. Comput. Sci.(2025) [dblp]
• VLDB J.(2025) [dblp]

Contents

ACNS (1) 2025

1. Oblivious Suffix Sorting: A Multi-Party Computation Scheme for Secure and Efficient Suffix Sorting.

COCOON (2) 2025

1. Revisit the Partial Coloring Method: Prefix Spencer and Sampling.

CPP 2025

1. Formalized Burrows-Wheeler Transform.

ICIC (26) 2025

1. Enough Consecutive Matches in k-Tuple Common Substrings.

IJTCS-FAW 2025

1. Finding a Set of Long Common Substrings with Repeats from m Input Strings.
2. k-Universality of Regular Languages Revisited.

RECOMB 2025

1. Prokrustean Graph: A Substring Index for Rapid K-Mer Size Analysis.

STOC 2025

1. On the Hardness Hierarchy for the O(n√log n) Complexity in the Word RAM.

Acta Informatica 2025

1. The Primitive Deficiency of two Primitive Strings.

Algorithms 2025

1. Substring Counting with Insertions.

Algorithms Mol. Biol. 2025

1. Faster computation of left-bounded shortest unique substrings.
2. sc McDag: indexing maximal common subsequences for k strings.

CoRR 2025

1. k-Universality of Regular Languages Revisited.
2. 25 Additional Problems - Extension to the Book “125 Problems in Text Algorithms”.
3. A Dynamic, Self-balancing k-d Tree.
4. A Framework for Building Data Structures from Communication Protocols.
5. A Space-Efficient Algorithm for Longest Common Almost Increasing Subsequence of Two Sequences.
6. A faster algorithm for efficient longest common substring calculation for non-parametric entropy estimation in sequential data.
7. Adaptive Hybrid Sort: Dynamic Strategy Selection for Optimal Sorting Across Diverse Data Distributions.
8. An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT.
9. Approximate Cartesian Tree Matching with One Difference.
10. Are Depth-2 Regular Expressions Hard to Intersect?
11. BWT for string collections.
12. Balanced Fibonacci word rectangles, and beyond.
13. Better Indexing for Rectangular Pattern Matching.
14. Binary Jumbled Indexing: Suffix tree histogram.
15. Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds.
16. Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms.
17. Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism.
18. Cartesian Forest Matching.
19. Checking and producing word attractors.
20. Cloitre’s Self-Generating Sequence.
21. Combinatorics of Palindromes.
22. Compact representation of maximal palindromes.
23. Compact representations of pattern-avoiding permutations.
24. Compressed Dictionary Matching on Run-Length Encoded Strings.
25. Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations.
26. Compressing Hypergraphs using Suffix Sorting.
27. Compressing Suffix Trees by Path Decompositions.
28. Computing k-mers in Graphs.
29. Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric.
30. Constant sensitivity on the CDAWGs.
31. Contextual Pattern Mining and Counting.
32. Counting Distinct Square Substrings in Sublinear Time.
33. Counting distinct (non-)crossing substrings.
34. Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform.
35. Depth first representations of k2-trees.
36. Deterministic Longest Common Subsequence Approximation in Near-Linear Time.
37. Digital Convexity and Combinatorics on Words.
38. Dorst-Smeulders Coding for Arbitrary Binary Words.
39. Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance.
40. Dynamic Indexing Through Learned Indices with Worst-case Guarantees.
41. Dynamic Necklace Splitting.
42. Dynamic Unit-Disk Range Reporting.
43. Dynamic r-index: An Updatable Self-Index for Highly Repetitive Strings.
44. Efficient Computation of Closed Substrings.
45. Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets.
46. Efficiently Finding All Minimal and Shortest Absent Subsequences in a String.
47. Encoding Co-Lex Orders of Finite-State Automata in Linear Space.
48. Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text.
49. Engineering Select Support for Hybrid Bitvectors.
50. Expected Length of the Longest Common Subsequence of Multiple Strings.
51. Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries.
52. Fast Computation of k-Runs, Parameterized Squares, and Other Generalised Squares.
53. Fast Pattern Matching with Epsilon Transitions.
54. Fast and memory-efficient BWT construction of repetitive texts using Lyndon grammars.
55. Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime.
56. Faster ED-String Matching with k Mismatches.
57. Fingerprint Filters Are Optimal.
58. Fully Dynamic LZ77 in Sublinear Time.
59. GPU Implementation of the Wavelet Tree.
60. Generalization of Repetitiveness Measures for Two-Dimensional Strings.
61. Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform.
62. Generalized Orthogonal de Bruijn Sequences.
63. IBB: Fast Burrows-Wheeler Transform Construction for Length-Diverse DNA Data.
64. Identifying Approximate Minimizers under Stochastic Uncertainty.
65. Improved Circular Dictionary Matching.
66. Improved Extended Regular Expression Matching.
67. Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves.
68. Improved Online Sorting.
69. Improving Merge Sort and Quick Sort Performance by Utilizing Alphadev’s Sorting Networks as Base Cases.
70. Indexing Strings with Utilities.
71. Indexing Tries within Entropy-Bounded Space.
72. Inverting Parameterized Burrows-Wheeler Transform.
73. Jumbled Scattered Factors.
74. KeBaB: k-mer based breaking for finding super-maximal exact matches.
75. LZD-style Compression Scheme with Truncation and Repetitions.
76. LZSE: an LZ-style compressor supporting O(log n)-time random access.
77. Lazy B-Trees.
78. Learned Static Function Data Structures.
79. Linear Time Subsequence and Supersequence Regex Matching.
80. Linear-space LCS enumeration with quadratic-time delay for two strings.
81. Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts.
82. Longest Unbordered Factors on Run-Length Encoded Strings.
83. Minimizers in Semi-Dynamic Strings.
84. Modern Minimal Perfect Hashing: A Survey.
85. Monochromatic arithmetic progressions in the Fibonacci word.
86. MorphisHash: Improving Space Efficiency of ShockHash for Minimal Perfect Hashing.
87. Morphisms and BWT-run Sensitivity.
88. Near-Optimal Property Testers for Pattern Matching.
89. Nearly Tight Bounds for the Online Sorting Problem.
90. Net Occurrences in Fibonacci and Thue-Morse Words.
91. New simple and fastest quicksort algorithm for equal keys.
92. Nyldon Factorization of Thue-Morse Words and Fibonacci Words.
93. OSTRICH2: Solver for Complex String Constraints.
94. Old and New Results on Alphabetic Codes.
95. On Minimizers of Minimum Density.
96. On a sequence of Kimberling and its relationship to the Tribonacci word.
97. On the Complexity of Finding Approximate LCS of Multiple Strings.
98. On the Hardness Hierarchy for the O(n √(log n)) Complexity in the Word RAM.
99. On the Smallest Size of Internal Collage Systems.
100. On the number of MUSs crossing a position.
101. On the sensitivity of CDAWG-grammars.
102. Online computation of normalized substring complexity.
103. Optimal Non-Oblivious Open Addressing.
104. Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings.
105. Optimal Static Fully Indexable Dictionaries.
106. Optimization of Base-n Radix Sort for Skewed Datasets.
107. PHast - Perfect Hashing with fast evaluation.
108. Pattern Matching under Weighted Edit Distance.
109. Pcodec: Better Compression for Numerical Sequences.
110. Permutation patterns in streams.
111. Practical colinear chaining on sequences revisited.
112. Prefix-free parsing for merging big BWTs.
113. Quantum Pattern Matching with Wildcards.
114. RLZ-r and LZ-End-r: Enhancing Move-r.
115. Random generation of universal cycles and de Bruijn sequences.
116. Resilient Pattern Mining.
117. Review of Three Variants of the k-d Tree.
118. Simple Quantum Algorithm for Approximate k-Mismatch Problem.
119. Simple in-place yet comparison-optimal Mergesort.
120. Smallest Suffixient Sets as a Repetitiveness Measure.
121. Sorting with constraints.
122. Space-Efficient k-Mismatch Text Indexes.
123. Static Retrieval Revisited: To Optimality and Beyond.
124. StrNim: a variant of Nim played on strings.
125. Streaming periodicity with mismatches, wildcards, and edits.
126. String Consensus Problems with Swaps and Substitutions.
127. String Matching with a Dynamic Pattern.
128. String Problems in the Congested Clique Model.
129. Subtree Mode and Applications.
130. Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck.
131. Succinct Preferential Attachment Graphs.
132. Symmetry of information for space-bounded online Kolmogorov complexity.
133. Testing Quasiperiodicity.
134. Testing Suffixient Sets.
135. Text Indexing and Pattern Matching with Ephemeral Edits.
136. The Complexity of Maximal Common Subsequence Enumeration.
137. The Narayana Morphism and Related Words.
138. The Structure of In-Place Space-Bounded Computation.
139. The Trie Measure, Revisited.
140. Theory Meets Practice for Bit Vectors Supporting Rank and Select.
141. Tight Additive Sensitivity on LZ-style Compressors and String Attractors.
142. Tight Lower Bounds for Central String Queries in Compressed Space.
143. Towards universally optimal sorting algorithms.
144. U-index: A Universal Indexing Framework for Matching Long Patterns.
145. Unclustered BWTs of any Length over Non-Binary Alphabets.
146. Universally Wheeler Languages.
147. Verified Purely Functional Catenable Real-Time Deques.
148. When is String Reconstruction using de Bruijn Graphs Hard?
149. Word Break on SLP-Compressed Texts.
150. Word Chain Generators for Prefix Normal Words.
151. Words with factor somplexity 2n+1 and minimal critical exponent.
152. Zip-Tries: Simple Dynamic Data Structures for Strings.
153. jXBW: Fast Substructure Search in Large-Scale JSONL Datasets for Foundation Model Applications.
154. persiansort : an alternative to mergesort inspired by persian rug.
155. r*-indexing.

Comput. J. 2025

1. Clustering-based compression for raster time series.

Eur. J. Comb. 2025

1. The asymptotic repetition threshold of sequences rich in palindromes.

Geo spatial Inf. Sci. 2025

1. Stronger compact representations of object trajectories.

Inf. Comput. 2025

1. Hardness and approximability of bounded access Lempel Ziv coding.
2. The generalized constrained longest common subsequence in the run-length encoded format.
3. The longest subsequence-duplicated subsequence and related problems.

Inf. Process. Lett. 2025

1. The longest common subsequence problem for small alphabets in the word RAM model.

Inf. Syst. 2025

1. Substring compression variations and LZ78-Derivates.
2. Two-level massive string dictionaries.

Int. J. Found. Comput. Sci. 2025

1. Repetition Factorization of Automatic Sequences.

J. Autom. Reason. 2025

1. Formally Verified Suffix Array Construction.

J. Heuristics 2025

1. Heuristics for the run-length encoded Burrows-Wheeler transform alphabet ordering problem.

J. Syst. Softw. 2025

1. On the compressibility of large-scale source code datasets.

Nat. Comput. 2025

1. Palindromes in adjacent factor swap of a word.

Pattern Anal. Appl. 2025

1. NEONATE: a bi-directional search strategy for non-overlapping pattern matching with gap constraint.

SoftwareX 2025

1. SDSL-Mobile: Enabling space-efficient data structures for mobile applications.

Theor. Comput. Sci. 2025

1. On the number of equal-letter runs of the bijective Burrows-Wheeler transform.
2. Repetitiveness measures based on string morphisms.
3. Subsequence covers of words.

VLDB J. 2025

1. Text indexing for long patterns using locally consistent anchors.

This site is open source. Improve this page.