StringologyTimes

CPM for Stringologist

CPM 2023

  1. Improving the Sensitivity of MinHash Through Hash-Value Analysis.
  2. Approximation Algorithms for the Longest Run Subsequence Problem.
  3. On the Impact of Morphisms on BWT-Runs.
  4. Encoding Hard String Problems with Answer Set Programming.
  5. Optimal LZ-End Parsing Is Hard.
  6. Faster Prefix-Sorting Algorithms for Deterministic Finite Automata.
  7. Compressed Indexing for Consecutive Occurrences.
  8. On Distances Between Words with Parameters.
  9. PalFM-Index: FM-Index for Palindrome Pattern Matching.
  10. Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond.
  11. Trie-Compressed Adaptive Set Intersection.
  12. MONI Can Find k-MEMs.
  13. From Bit-Parallelism to Quantum String Matching for Labelled Graphs.
  14. Merging Sorted Lists of Similar Strings.
  15. MUL-Tree Pruning for Consistency and Compatibility.
  16. Suffix-Prefix Queries on a Dictionary.
  17. Order-Preserving Squares in Strings.
  18. Optimal Near-Linear Space Heaviest Induced Ancestors.
  19. Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String.
  20. Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor.
  21. Computing MEMs on Repetitive Text Collections.
  22. Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications.
  23. On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem.
  24. L-Systems for Measuring Repetitiveness.
  25. String Factorization via Prefix Free Families.
  26. Sliding Window String Indexing in Streams.

CPM 2022

  1. The Dynamic k-Mismatch Problem.
  2. Bi-Directional r-Indexes.
  3. Longest Palindromic Substring in Sublinear Time.

CPM 2021

  1. Efficient Algorithms for Counting Gapped Palindromes.
  2. R-enum: Enumeration of Characteristic Substrings in BWT-runs Bounded Space.
  3. Compressed Weighted de Bruijn Graphs.
  4. Ranking Bracelets in Polynomial Time.
  5. The Longest Run Subsequence Problem: Further Complexity Results.
  6. A Compact Index for Cartesian Tree Matching.
  7. Constructing Strings Avoiding Forbidden Substrings.
  8. Disorders and Permutations.
  9. String Sanitization Under Edit Distance: Improved and Generalized.
  10. Repetitions in Strings: A “Constant” Problem (Invited Talk).
  11. Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time.
  12. Optimal Completion and Comparison of Incomplete Phylogenetic Trees Under Robinson-Foulds Distance.
  13. AWLCO: All-Window Length Co-Occurrence.
  14. Internal Shortest Absent Word Queries.
  15. A Fast and Small Subsampled R-Index.
  16. Computing Covers of 2D-Strings.
  17. On-Line Pattern Matching on D-Texts (Invited Talk).
  18. Weighted Ancestors in Suffix Trees Revisited.
  19. The k-Mappability Problem Revisited.
  20. Data Structures for Categorical Path Counting Queries.
  21. Optimal Construction of Hierarchical Overlap Graphs.
  22. An Invertible Transform for Efficient String Matching in Labeled Digraphs.
  23. Gapped Indexing for Consecutive Occurrences.
  24. A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs.
  25. Computing Edit Distance (Invited Talk).

CPM 2020

  1. Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions.
  2. Detecting k-(Sub-)Cadences and Equidistant Subsequence Occurrences.
  3. k-Approximate Quasiperiodicity under Hamming and Edit Distance.
  4. Time-Space Tradeoffs for Finding a Long Common Substring.
  5. Longest Common Subsequence on Weighted Sequences.
  6. Counting Distinct Patterns in Internal Dictionary Matching.
  7. Efficient Tree-Structured Categorical Retrieval.
  8. On Indeterminate Strings Matching.
  9. String Sanitization Under Edit Distance.
  10. FM-Index Reveals the Reverse Suffix Array.
  11. Double String Tandem Repeats.
  12. DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures.
  13. On Extensions of Maximal Repeats in Compressed Strings.
  14. Dynamic String Alignment.
  15. On Two Measures of Distance Between Fully-Labelled Trees.
  16. Approximating Longest Common Substring with k mismatches: Theory and Practice.
  17. Genomic Problems Involving Copy Number Profiles: Complexity and Algorithms.
  18. Approximating Text-To-Pattern Distance via Dimensionality Reduction.
  19. Faster Binary Mean Computation Under Dynamic Time Warping.
  20. Parameterized Algorithms for Matrix Completion with Radius Constraints.
  21. Compressed Orthogonal Search on Suffix Arrays with Applications to Range LCP.
  22. The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time.
  23. String Factorizations Under Various Collision Constraints.
  24. Finding the Anticover of a String.
  25. Unary Words Have the Smallest Levenshtein k-Neighbourhoods.
  26. Algebraic Algorithms for Finding Patterns in Graphs (Invited Talk).
  27. Chaining with Overlaps Revisited.
  28. Text Indexing and Searching in Sublinear Time.
  29. In-Place Bijective Burrows-Wheeler Transforms.

CPM 2019

  1. On the Size of Overlapping Lempel-Ziv and Lyndon Factorizations.
  2. A Rearrangement Distance for Fully-Labelled Trees.
  3. Online Algorithms for Constructing Linear-Size Suffix Trie.
  4. Linking BWT and XBW via Aho-Corasick Automaton: Applications to Run-Length Encoding.
  5. Computing the Antiperiod(s) of a String.
  6. Conversion from RLBWT to LZ77.
  7. Some Variations on Lyndon Words (Invited Talk).
  8. Cartesian Tree Matching and Indexing.
  9. Fully-Functional Bidirectional Burrows-Wheeler Indexes and Infinite-Order De Bruijn Graphs.
  10. Quasi-Periodicity in Streams.
  11. Sufficient Conditions for Efficient Indexing Under Different Matchings.
  12. Indexing the Bijective BWT.
  13. Hamming Distance Completeness.
  14. A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem.
  15. Compressed Multiple Pattern Matching.
  16. Searching Long Repeats in Streams.
  17. Approximating Approximate Pattern Matching.
  18. Finding a Small Number of Colourful Components.
  19. Entropy Lower Bounds for Dictionary Compression.
  20. Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform.
  21. On Maximal Repeats in Compressed Strings.
  22. Quasi-Linear-Time Algorithm for Longest Common Circular Factor.
  23. Optimal Rank and Select Queries on Dictionary-Compressed Text.
  24. A New Class of Searchable and Provably Highly Compressible String Transformations.
  25. How to Exploit Periodicity (Invited Talk).
  26. Streaming Dictionary Matching with Mismatches.
  27. Stringology Combats Microbiological Threats (Invited Talk).
  28. Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to RNA Folding.
  29. Faster Queries for Longest Substring Palindrome After Block Edit.
  30. Computing Runs on a Trie.
  31. Dichotomic Selection on Words: A Probabilistic Analysis.
  32. Simulating the DNA Overlap Graph in Succinct Space.

CPM 2018

  1. Linear-Time Algorithm for Long LCF with k Mismatches.
  2. On Undetected Redundancy in the Burrows-Wheeler Transform.
  3. Slowing Down Top Trees for Better Worst-Case Compression.
  4. Order-Preserving Pattern Matching Indeterminate Strings.
  5. Lyndon Factorization of Grammar Compressed Texts Revisited.
  6. Longest substring palindrome after edit.
  7. Maximal Common Subsequence Algorithms.
  8. Faster Online Elastic Degenerate String Matching.
  9. Computing longest common square subsequences.
  10. Online LZ77 Parsing and Matching Statistics with RLBWTs.
  11. Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms.
  12. Longest Lyndon Substring After Edit.

CPM 2017

  1. Lempel-Ziv Compression in a Sliding Window.
  2. Tight Bounds on the Maximum Number of Shortest Unique Substrings.
  3. Palindromic Length in Linear Time.
  4. From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back.
  5. Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing.
  6. Communication and Streaming Complexity of Approximate Pattern Matching.
  7. Computing All Distinct Squares in Linear Time for Integer Alphabets.
  8. Wheeler Graphs: Variations on a Theme by Burrows and Wheeler.
  9. Longest Common Extensions with Recompression.
  10. Deterministic Indexing for Packed Strings.
  11. Representing the Suffix Tree with the CDAWG.
  12. Faster STR-IC-LCS Computation via RLE.
  13. Document Listing on Repetitive Collections with Guaranteed Performance.
  14. Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings.
  15. Can We Recover the Cover?.
  16. On-Line Pattern Matching on Similar Texts.
  17. Path Queries on Functions.
  18. Approximate Cover of Strings.

CPM 2016

  1. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
  2. Boxed Permutation Pattern Matching.
  3. The Nearest Colored Node in a Tree.
  4. Minimal Suffix and Rotation of a Substring in Optimal Time.
  5. On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching.
  6. Space-Efficient Dictionaries for Parameterized and Order-Preserving Pattern Matching.
  7. Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction.
  8. Efficient Index for Weighted Sequences.
  9. Fully-online Construction of Suffix Trees for Multiple Texts.
  10. Longest Common Substring with Approximately k Mismatches.
  11. Faster Longest Common Extension Queries in Strings over General Alphabets.
  12. Factorizing a String into Squares in Linear Time.

CPM 2015

  1. Online Detection of Repetitions with Backtracking.
  2. Tighter Bounds for the Sum of Irreducible LCP Values.
  3. Longest Common Extensions in Sublinear Space.
  4. Composite Repetition-Aware Data Structures.
  5. Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree.
  6. Compact Indexes for Flexible Top- k k Retrieval.
  7. Lempel Ziv Computation in Small Space (LZ-CISS).
  8. Alphabet-Dependent String Searching with Wexponential Search Trees.
  9. Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints.
  10. A Framework for Space-Efficient String Kernels.
  11. On Maximal Unbordered Factors.
  12. Longest Common Extensions in Trees.
  13. Parallel External Memory Suffix Sorting.
  14. LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding.

CPM 2014

  1. Computing Minimal and Maximal Suffixes of a Substring Revisited.
  2. Approximate On-line Palindrome Recognition, and Applications.
  3. Encodings for Range Majority Queries.
  4. Dictionary Matching with One Gap.
  5. A really Simple Approximation of Smallest Grammar.
  6. Most Recent Match Queries in On-Line Suffix Trees.
  7. Permuted Scaled Matching.
  8. Indexed Geometric Jumbled Pattern Matching.
  9. Efficient Algorithms for Shortest Partial Seeds in Words.
  10. Compressed Subsequence Matching and Packed Tree Coloring.
  11. String Range Matching.
  12. Computing Palindromic Factorizations and Palindromic Covers On-line.
  13. Order-Preserving Pattern Matching with k Mismatches.

CPM 2013

  1. New Algorithms for Position Heaps.
  2. On Minimal and Maximal Suffixes of a Substring.
  3. Time-Space Trade-Offs for the Longest Common Substring Problem.
  4. A Succinct Grammar Compression.
  5. Linear Time Lempel-Ziv Factorization: Simple, Fast, Small.
  6. Compact q-Gram Profiling of Compressed Strings.
  7. Converting SLP to LZ78 in almost Linear Time.
  8. Efficient Lyndon Factorization of Grammar Compressed Text.
  9. Document Listing on Repetitive Collections.
  10. Fast Algorithm for Partial Covers in Words.

CPM 2012

  1. Cross-Document Pattern Matching.
  2. Speeding Up q-Gram Mining on Grammar-Based Compressed Texts.
  3. Constant-Time Word-Size String Matching.
  4. Wavelet Trees for All.
  5. Simple and Efficient LZW-Compressed Multiple Pattern Matching.
  6. Time-Space Trade-Offs for Longest Common Extensions.
  7. Compressed String Dictionary Look-Up with Edit Distance One.

CPM 2011

  1. Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts.
  2. Self-indexing Based on LZ77.
  3. On the Weak Prefix-Search Problem.
  4. Efficient Seeds Computation Revisited.
  5. LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations.
  6. Substring Range Reporting.
  7. Palindrome Pattern Matching.
  8. Counting Colours in Compressed Strings.
  9. Lempel-Ziv Factorization Revisited.

CPM 2010

  1. Verifying a Parameterized Border Array in O(n1.5) Time.
  2. Parallel and Distributed Compressed Indexes.
  3. Approximate All-Pairs Suffix/Prefix Overlaps.
  4. Bidirectional Search in a String with Wavelet Trees.
  5. Succinct Dictionary Matching with No Slowdown.

CPM 2009

  1. Permuted Longest-Common-Prefix Array.
  2. On the Value of Multiple Read/Write Streams for Data Compression.
  3. Fast Searching in Packed Strings.
  4. Faster and Space-Optimal Edit Distance “1” Dictionary.

CPM 2008

  1. Lower Bounds for Succinct Data Structures.
  2. On-Line Approximate String Matching with Bounded Errors.
  3. Dynamic Fully-Compressed Suffix Trees.
  4. An(other) Entropy-Bounded Compressed Suffix Tree.

CPM 2007

  1. Fast and Practical Algorithms for Computing All the Runs in a String.
  2. Move-to-Front, Distance Coding, and Inversion Frequencies Revisited.
  3. A Lempel-Ziv Text Index on Secondary Storage.
  4. Suffix Arrays on Words.
  5. Space-Efficient Algorithms for Document Retrieval.
  6. Efficient Computation of Substring Equivalence Classes with Suffix Arrays.
  7. Compressed Text Indexes with Fast Locate.
  8. Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts.

CPM 2006

  1. Reducing the Space Requirement of LZ-Index.
  2. On-Line Linear-Time Construction of Word Suffix Trees.
  3. Statistical Encoding of Succinct Data Structures.
  4. Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents.
  5. Dynamic Entropy-Compressed Sequences and Full-Text Indexes.

CPM 2005

  1. DNA Compression Challenge Revisited: A Dynamic Programming Approach.
  2. Succinct Suffix Arrays Based on Run-Length Encoding.

CPM 2004

  1. Real-Time String Matching in Sublinear Space.
  2. Compressed Compact Suffix Arrays.
  3. Improved Single and Multiple Approximate String Matching.

CPM 2003

  1. Average-Optimal Multiple Approximate String Matching.
  2. A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression.
  3. On Minimizing Pattern Splitting in Multi-track String Matching.

CPM 2002

  1. Local Similarity Based Point-Pattern Matching.
  2. Space-Economical Algorithms for Finding Maximal Unique Matches.
  3. Faster Bit-Parallel Approximate String Matching.
  4. Optimal Exact and Fast Approximate Two Dimensional Pattern Matching Allowing Rotations.
  5. Edit Distance with Move Operations.
  6. The Minimum DAWG for All Suffixes of a String and Its Applications.

CPM 2001

  1. Regular Expression Searching over Ziv-Lempel Compressed Text.
  2. Efficient Discovery of Proximity Patterns with Suffix Arrays.
  3. Approximate Matching of Run-Length Compressed Strings.
  4. Multiple Pattern Matching Algorithms on Collage System.
  5. On-Line Construction of Compact Directed Acyclic Word Graphs.

CPM 2000

  1. Approximate String Matching over Ziv-Lempel Compressed Text.
  2. Compact Suffix Array.
  3. Indexing Text with Approximate q-Grams.
  4. Boyer-Moore String Matching over Ziv-Lempel Compressed Text.
  5. A Boyer-Moore Type Algorithm for Compressed Pattern Matching.

CPM 1999

  1. A General Practical Approach to Pattern Matching over Ziv-Lempel Compressed Text.
  2. Shift-And Approach to Pattern Matching in LZW Compressed Text.
  3. Fast Multi-dimensional Approximate Pattern Matching.
  4. A New Indexing Method for Approximate String Matching.

CPM 1998

  1. A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching.

CPM 1997

  1. Distributed Generation of Suffix Arrays.

CPM 1996

  1. Suffix Trees on Words.
  2. A Faster Algorithm for Approximate String Matching.
This site is open source. Improve this page.