StringologyTimes

CPM for Stringologist

CPM 2025

  1. Net Occurrences in Fibonacci and Thue-Morse Words.
  2. Improved Circular Dictionary Matching.
  3. Text Indexing for Simple Regular Expressions.
  4. Faster Approximate Elastic-Degenerate String Matching - Part B.
  5. String Problems in the Congested Clique Model.
  6. A Family of Partial Cubes with Minimal Fibonacci Dimension.
  7. Branch Prediction Analysis of Morris-Pratt and Knuth-Morris-Pratt Algorithms.
  8. On Palindromic Periodicities.
  9. On the Compressiveness of the Burrows-Wheeler Transform.
  10. Pattern Matching on Run-Length Grammar-Compressed Strings in Linear Time.
  11. Compressed Dictionary Matching on Run-Length Encoded Strings.
  12. Covers in Optimal Space.
  13. The Trie Measure, Revisited.
  14. Extending the Burrows-Wheeler Transform for Cartesian Tree Matching and Constructing It.
  15. Encodings for Range Minimum Queries over Bounded Alphabets.
  16. Sorted Consecutive Occurrence Queries in Substrings.
  17. Faster Approximate Elastic-Degenerate String Matching - Part A.
  18. Encoding Co-Lex Orders of Finite-State Automata in Linear Space.
  19. Front Matter, Table of Contents, Preface, Conference Organization.
  20. Counting on General Run-Length Grammars.
  21. FL-RMQ: A Learned Approach to Range Minimum Queries.
  22. Linear-Space LCS Enumeration for Two Strings.
  23. Generating a Cyclic 2-Gray Code for Lucas Words in Constant Amortized Time.
  24. Succinct Data Structures for Segments.
  25. The Equivalence Problem of E-Pattern Languages with Length Constraints Is Undecidable.
  26. Minimal Generators in Optimal Time.
  27. Space-Efficient Online Computation of String Net Occurrences.
  28. Doubly-Periodic String Comparison.
  29. Shortest Undirected Paths in de Bruijn Graphs.
  30. Representing Paths in Digraphs.

CPM 2024

  1. Algorithms for Galois Words: Detection, Factorization, and Rotation.
  2. Random Wheeler Automata.
  3. Faster Sliding Window String Indexing in Streams.
  4. The Rational Construction of a Wheeler DFA.
  5. A Data Structure for the Maximum-Sum Segment Problem with Offsets.
  6. Searching 2D-Strings for Matching Frames.
  7. Shortest Cover After Edit.
  8. Simplified Tight Bounds for Monotone Minimal Perfect Hashing.
  9. Internal Pattern Matching in Small Space and Applications.
  10. Minimizing the Minimizers via Alphabet Reordering.
  11. When Is the Normalized Edit Distance over Non-Uniform Weights a Metric?
  12. Hairpin Completion Distance Lower Bound.
  13. Closing the Gap: Minimum Space Optimal Time Distance Labeling Scheme for Interval Graphs.
  14. Front Matter, Table of Contents, Preface, Conference Organization.
  15. A Class of Heuristics for Reducing the Number of BWT-Runs in the String Ordering Problem.
  16. Efficient Construction of Long Orientable Sequences.
  17. Finding Diverse Strings and Longest Common Subsequences in a Graph.
  18. Subsequences with Generalised Gap Constraints: Upper and Lower Complexity Bounds.
  19. Connecting de Bruijn Graphs.
  20. Walking on Words.
  21. Solving the Minimal Positional Substring Cover Problem in Sublinear Space.
  22. Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space.
  23. Maintaining the Size of LZ77 on Semi-Dynamic Strings.
  24. Computing the LCP Array of a Labeled Graph.
  25. Reconstructing General Matching Graphs.
  26. Tight Bounds for Compressing Substring Samples.
  27. Online Context-Free Recognition in OMv Time.
  28. Exploiting New Properties of String Net Frequency for Efficient Computation.
  29. BAT-LZ out of hell.

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. Front Matter, Table of Contents, Preface, Conference Organization.
  6. Optimal LZ-End Parsing Is Hard.
  7. Faster Prefix-Sorting Algorithms for Deterministic Finite Automata.
  8. Compressed Indexing for Consecutive Occurrences.
  9. On Distances Between Words with Parameters.
  10. PalFM-Index: FM-Index for Palindrome Pattern Matching.
  11. Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond.
  12. Trie-Compressed Adaptive Set Intersection.
  13. MONI Can Find k-MEMs.
  14. From Bit-Parallelism to Quantum String Matching for Labelled Graphs.
  15. Merging Sorted Lists of Similar Strings.
  16. MUL-Tree Pruning for Consistency and Compatibility.
  17. Suffix-Prefix Queries on a Dictionary.
  18. Order-Preserving Squares in Strings.
  19. Optimal Near-Linear Space Heaviest Induced Ancestors.
  20. Linear-Time Computation of Cyclic Roots and Cyclic Covers of a String.
  21. Faster Algorithms for Computing the Hairpin Completion Distance and Minimum Ancestor.
  22. Computing MEMs on Repetitive Text Collections.
  23. Comparing Elastic-Degenerate Strings: Algorithms, Lower Bounds, and Applications.
  24. On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem.
  25. L-Systems for Measuring Repetitiveness.
  26. String Factorization via Prefix Free Families.
  27. Sliding Window String Indexing in Streams.

CPM 2022

  1. Invitation to Combinatorial Reconfiguration (Invited Talk).
  2. A Theoretical and Experimental Analysis of BWT Variants for String Collections.
  3. Reordering a Tree According to an Order on Its Leaves.
  4. {RePair} Grammars Are the Smallest Grammars for Fibonacci Words.
  5. Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants.
  6. Efficient Construction of the BWT for Repetitive Text Using String Compression.
  7. Permutation Pattern Matching for Doubly Partially Ordered Patterns.
  8. Linear-Time Computation of Shortest Covers of All Rotations of a String.
  9. Rectangular Tile Covers of 2D-Strings.
  10. Parallel Algorithm for Pattern Matching Problems Under Substring Consistent Equivalence Relations.
  11. Indexable Elastic Founder Graphs of Minimum Height.
  12. Minimal Absent Words on Run-Length Encoded Strings.
  13. Making de Bruijn Graphs Eulerian.
  14. The Dynamic k-Mismatch Problem.
  15. Bi-Directional r-Indexes.
  16. Using Automata and a Decision Procedure to Prove Results in Pattern Matching (Invited Talk).
  17. An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions.
  18. Mechanical Proving with Walnut for Squares and Cubes in Partial Words.
  19. The Normalized Edit Distance with Uniform Operation Costs Is a Metric.
  20. Back-To-Front Online Lyndon Forest Construction.
  21. Arbitrary-Length Analogs to de Bruijn Sequences.
  22. Cartesian Tree Subsequence Matching.
  23. Front Matter, Table of Contents, Preface, Conference Organization.
  24. Beyond the Longest Letter-Duplicated Subsequence Problem.
  25. Partial Permutations Comparison, Maintenance and Applications.
  26. Compact Text Indexing for Advanced Pattern Matching Problems: Parameterized, Order-Isomorphic, 2D, etc. (Invited Talk).
  27. The Fine-Grained Complexity of Episode Matching.
  28. Reduction Ratio of the IS-Algorithm: Worst and Random Cases.
  29. On Strings Having the Same Length- k Substrings.
  30. 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. Front Matter, Table of Contents, Preface, Conference Organization.
  5. Ranking Bracelets in Polynomial Time.
  6. The Longest Run Subsequence Problem: Further Complexity Results.
  7. A Compact Index for Cartesian Tree Matching.
  8. Constructing Strings Avoiding Forbidden Substrings.
  9. Disorders and Permutations.
  10. String Sanitization Under Edit Distance: Improved and Generalized.
  11. Repetitions in Strings: A “Constant” Problem (Invited Talk).
  12. Constructing the Bijective and the Extended Burrows-Wheeler Transform in Linear Time.
  13. Optimal Completion and Comparison of Incomplete Phylogenetic Trees Under Robinson-Foulds Distance.
  14. AWLCO: All-Window Length Co-Occurrence.
  15. Internal Shortest Absent Word Queries.
  16. A Fast and Small Subsampled R-Index.
  17. Computing Covers of 2D-Strings.
  18. On-Line Pattern Matching on D-Texts (Invited Talk).
  19. Weighted Ancestors in Suffix Trees Revisited.
  20. The k-Mappability Problem Revisited.
  21. Data Structures for Categorical Path Counting Queries.
  22. Optimal Construction of Hierarchical Overlap Graphs.
  23. An Invertible Transform for Efficient String Matching in Labeled Digraphs.
  24. Gapped Indexing for Consecutive Occurrences.
  25. A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs.
  26. 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. Front Matter, Table of Contents, Preface, Conference Organization.
  21. Parameterized Algorithms for Matrix Completion with Radius Constraints.
  22. Compressed Orthogonal Search on Suffix Arrays with Applications to Range LCP.
  23. The Streaming k-Mismatch Problem: Tradeoffs Between Space and Total Time.
  24. String Factorizations Under Various Collision Constraints.
  25. Finding the Anticover of a String.
  26. Unary Words Have the Smallest Levenshtein k-Neighbourhoods.
  27. Algebraic Algorithms for Finding Patterns in Graphs (Invited Talk).
  28. Chaining with Overlaps Revisited.
  29. Text Indexing and Searching in Sublinear Time.
  30. 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. Front Matter, Table of Contents, Preface, Conference Organization.
  18. Approximating Approximate Pattern Matching.
  19. Finding a Small Number of Colourful Components.
  20. Entropy Lower Bounds for Dictionary Compression.
  21. Space-Efficient Computation of the LCP Array from the Burrows-Wheeler Transform.
  22. On Maximal Repeats in Compressed Strings.
  23. Quasi-Linear-Time Algorithm for Longest Common Circular Factor.
  24. Optimal Rank and Select Queries on Dictionary-Compressed Text.
  25. A New Class of Searchable and Provably Highly Compressible String Transformations.
  26. How to Exploit Periodicity (Invited Talk).
  27. Streaming Dictionary Matching with Mismatches.
  28. Stringology Combats Microbiological Threats (Invited Talk).
  29. Safe and Complete Algorithms for Dynamic Programming Problems, with an Application to RNA Folding.
  30. Faster Queries for Longest Substring Palindrome After Block Edit.
  31. Computing Runs on a Trie.
  32. Dichotomic Selection on Words: A Probabilistic Analysis.
  33. Simulating the DNA Overlap Graph in Succinct Space.

CPM 2018

  1. A Succinct Four Russians Speedup for Edit Distance Computation and One-against-many Banded Alignment.
  2. Linear-time algorithms for the subpath kernel.
  3. Linear-Time Algorithm for Long LCF with k Mismatches.
  4. On Undetected Redundancy in the Burrows-Wheeler Transform.
  5. Slowing Down Top Trees for Better Worst-Case Compression.
  6. Order-Preserving Pattern Matching Indeterminate Strings.
  7. Nearest constrained circular words.
  8. Lyndon Factorization of Grammar Compressed Texts Revisited.
  9. Non-Overlapping Indexing - Cache Obliviously.
  10. A Simple Linear-Time Algorithm for Computing the Centroid and Canonical Form of a Plane Graph and Its Applications.
  11. Quasi-Periodicity Under Mismatch Errors.
  12. Longest substring palindrome after edit.
  13. Fast Matching-based Approximations for Maximum Duo-Preservation String Mapping and its Weighted Variant.
  14. Maximal Common Subsequence Algorithms.
  15. Faster Online Elastic Degenerate String Matching.
  16. Computing longest common square subsequences.
  17. The Heaviest Induced Ancestors Problem Revisited.
  18. Online LZ77 Parsing and Matching Statistics with RLBWTs.
  19. Dualities in Tree Representations.
  20. Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms.
  21. Superstrings with multiplicities.
  22. Longest Lyndon Substring After Edit.
  23. Can a permutation be sorted by best short swaps?.
  24. On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph Structure.
  25. Front Matter, Table of Contents, Preface, Conference Organization.

CPM 2017

  1. Lempel-Ziv Compression in a Sliding Window.
  2. Front Matter, Table of Contents, Preface, Conference Organization, External Reviewers.
  3. Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars.
  4. Tight Bounds on the Maximum Number of Shortest Unique Substrings.
  5. Palindromic Length in Linear Time.
  6. Shortest Superstring.
  7. From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back.
  8. Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing.
  9. Communication and Streaming Complexity of Approximate Pattern Matching.
  10. Computing All Distinct Squares in Linear Time for Integer Alphabets.
  11. Position Heaps for Parameterized Strings.
  12. Wheeler Graphs: Variations on a Theme by Burrows and Wheeler.
  13. Longest Common Extensions with Recompression.
  14. Deterministic Indexing for Packed Strings.
  15. Gapped Pattern Statistics.
  16. Representing the Suffix Tree with the CDAWG.
  17. Revisiting the Parameterized Complexity of Maximum-Duo Preservation String Mapping.
  18. Faster STR-IC-LCS Computation via RLE.
  19. On the Weighted Quartet Consensus Problem.
  20. Dynamic Elias-Fano Representation.
  21. Document Listing on Repetitive Collections with Guaranteed Performance.
  22. Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings.
  23. Optimal Omnitig Listing for Safe and Complete Contig Assembly.
  24. Can We Recover the Cover?.
  25. The Longest Filled Common Subsequence Problem.
  26. Beyond Adjacency Maximization: Scaffold Filling for New String Distances.
  27. Synergistic Solutions on MultiSets.
  28. On-Line Pattern Matching on Similar Texts.
  29. Path Queries on Functions.
  30. Recompression of SLPs.
  31. Approximate Cover of Strings.
  32. A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem.

CPM 2016

  1. Color-Distance Oracles and Snippets.
  2. Succinct Online Dictionary Matching with Improved Worst-Case Guarantees.
  3. Finding Maximal 2-Dimensional Palindromes.
  4. Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams.
  5. Boxed Permutation Pattern Matching.
  6. Reconstruction of Trees from Jumbled and Weighted Subtrees.
  7. Efficient Non-Binary Gene Tree Resolution with Weighted Reconciliation Cost.
  8. The Nearest Colored Node in a Tree.
  9. Minimal Suffix and Rotation of a Substring in Optimal Time.
  10. Genomic Scaffold Filling Revisited.
  11. Fast Compatibility Testing for Rooted Phylogenetic Trees.
  12. Graph Motif Problems Parameterized by Dual.
  13. Linear-time Suffix Sorting - A New Approach for Suffix Array Construction.
  14. Hardness of RNA Folding Problem With Four Symbols.
  15. On the Benefit of Merging Suffix Array Intervals for Parallel Pattern Matching.
  16. Space-Efficient Dictionaries for Parameterized and Order-Preserving Pattern Matching.
  17. Deterministic Sub-Linear Space LCE Data Structures With Efficient Construction.
  18. Front Matter, Table of Contents, Preface.
  19. Efficient Index for Weighted Sequences.
  20. A 7/2-Approximation Algorithm for the Maximum Duo-Preservation String Mapping Problem.
  21. Fully-online Construction of Suffix Trees for Multiple Texts.
  22. Longest Common Substring with Approximately k Mismatches.
  23. Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.
  24. Estimating Statistics on Words Using Ambiguous Descriptions.
  25. A Linear-Time Algorithm for the Copy Number Transformation Problem.
  26. On Almost Monge All Scores Matrices.
  27. Faster Longest Common Extension Queries in Strings over General Alphabets.
  28. Encoding Two-Dimensional Range Top-k Queries.
  29. Factorizing a String into Squares in Linear Time.
  30. Optimal Prefix Free Codes with Partial Sorting.

CPM 2015

  1. Online Detection of Repetitions with Backtracking.
  2. Ranked Document Retrieval with Forbidden Pattern.
  3. On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling.
  4. Tighter Bounds for the Sum of Irreducible LCP Values.
  5. Sorting by Cuts, Joins and Whole Chromosome Duplications.
  6. String Powers in Trees.
  7. Parameterized Complexity of Superstring Problems.
  8. Fast String Dictionary Lookup with One Error.
  9. The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets.
  10. Longest Common Extensions in Sublinear Space.
  11. Dictionary Matching with Uneven Gaps.
  12. Composite Repetition-Aware Data Structures.
  13. Succinct Non-overlapping Indexing.
  14. Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis.
  15. Combinatorial RNA Design: Designability and Structure-Approximating Algorithm.
  16. Encodings of Range Maximum-Sum Segment Queries and Applications.
  17. Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree.
  18. Greedy Conjecture for Strings of Length 4.
  19. Compact Indexes for Flexible Top- k k Retrieval.
  20. Lempel Ziv Computation in Small Space (LZ-CISS).
  21. Alphabet-Dependent String Searching with Wexponential Search Trees.
  22. Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints.
  23. Range Minimum Query Indexes in Higher Dimensions.
  24. A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm.
  25. A Framework for Space-Efficient String Kernels.
  26. Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process.
  27. On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem.
  28. Encoding Nearest Larger Values.
  29. On Maximal Unbordered Factors.
  30. Longest Common Extensions in Trees.
  31. On the Readability of Overlap Digraphs.
  32. Parallel External Memory Suffix Sorting.
  33. Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem.
  34. 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. On the Efficiency of the Hamming C-Centerstring Problems.
  4. Approximate String Matching Using a Bidirectional Index.
  5. Compactness-Preserving Mapping on Trees.
  6. The Worst Case Complexity of Maximum Parsimony.
  7. Encodings for Range Majority Queries.
  8. Dictionary Matching with One Gap.
  9. A really Simple Approximation of Smallest Grammar.
  10. Most Recent Match Queries in On-Line Suffix Trees.
  11. Shortest Unique Substring Query Revisited.
  12. Parameterized Complexity Analysis for the Closest String with Wildcards Problem.
  13. Permuted Scaled Matching.
  14. Randomized and Parameterized Algorithms for the Closest String Problem.
  15. Indexed Geometric Jumbled Pattern Matching.
  16. Efficient Algorithms for Shortest Partial Seeds in Words.
  17. Compressed Subsequence Matching and Packed Tree Coloring.
  18. On Hardness of Several String Indexing Problems.
  19. Computing k-th Lyndon Word and Decoding Lexicographically Minimal de Bruijn Sequence.
  20. String Range Matching.
  21. An Improved Query Time for Succinct Dynamic Dictionary Matching.
  22. Reversal Distances for Strings with Few Blocks or Small Alphabets.
  23. On Combinatorial Generation of Prefix Normal Words.
  24. Computing Palindromic Factorizations and Palindromic Covers On-line.
  25. On the DCJ Median Problem.
  26. From Indexing Data Structures to de Bruijn Graphs.
  27. Searching of Gapped Repeats and Subrepetitions in a Word.
  28. Order-Preserving Pattern Matching with k Mismatches.

CPM 2013

  1. Locating All Maximal Approximate Runs in a String.
  2. Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings.
  3. New Algorithms for Position Heaps.
  4. On Minimal and Maximal Suffixes of a Substring.
  5. Time-Space Trade-Offs for the Longest Common Substring Problem.
  6. A Succinct Grammar Compression.
  7. Forty Years of Text Indexing.
  8. Pattern Matching with Variables: A Multivariate Complexity Analysis.
  9. Linear Time Lempel-Ziv Factorization: Simple, Fast, Small.
  10. Compact q-Gram Profiling of Compressed Strings.
  11. A Constant-Space Comparison-Based Algorithm for Computing the Burrows-Wheeler Transform.
  12. Converting SLP to LZ78 in almost Linear Time.
  13. LCP Magic.
  14. External Memory Generalized Suffix and LCP Arrays Construction.
  15. Approximating Shortest Superstring Problem Using de Bruijn Graphs.
  16. Approximation of Grammar-Based Compression via Recompression.
  17. Local Search for String Problems: Brute Force Is Essentially Optimal.
  18. Discrete Methods for Image Analysis Applied to Molecular Biology.
  19. Space-Efficient Construction Algorithm for the Circular Suffix Tree.
  20. Efficient Lyndon Factorization of Grammar Compressed Text.
  21. Document Listing on Repetitive Collections.
  22. Efficient All Path Score Computations on Grid Graphs.
  23. Fast Algorithm for Partial Covers in Words.
  24. A Bit-Parallel, General Integer-Scoring Sequence Alignment Algorithm.

CPM 2012

  1. Near Linear Time Construction of an Approximate Index for All Maximum Consecutive Sub-sums of a Sequence.
  2. Cross-Document Pattern Matching.
  3. FEMTO: Fast Search of Large Sequence Collections.
  4. Document Listing for Queries with Excluded Pattern.
  5. Minimum Leaf Removal for Reconciliation: Complexity and Algorithms.
  6. Speeding Up q-Gram Mining on Grammar-Based Compressed Texts.
  7. Local Exact Pattern Matching for Non-fixed RNA Structures.
  8. Gene Regulation, Protein Networks and Disease: A Computational Perspective.
  9. Computing the Rooted Triplet Distance between Galled Trees by Counting Triangles.
  10. Hardness of Longest Common Subsequence for Sequences with Bounded Run-Lengths.
  11. Constant-Time Word-Size String Matching.
  12. On Approximating String Selection Problems with Outliers.
  13. The Parameterized Complexity of the Shared Center Problem.
  14. Efficient Algorithm for Circular Burrows-Wheeler Transform.
  15. Efficient Exponential Time Algorithms for Edit Distance between Unordered Trees.
  16. Impact of the Energy Model on the Complexity of RNA Folding with Pseudoknots.
  17. A Linear Kernel for the Complementary Maximal Strip Recovery Problem.
  18. Wavelet Trees for All.
  19. Efficient Two-Dimensional Pattern Matching with Scaling and Rotation and Higher-Order Interpolation.
  20. Approximation Algorithms and Hardness Results for Shortest Path Based Graph Orientations.
  21. Least Random Suffix/Prefix Matches in Output-Sensitive Time.
  22. Fixed-Parameter Algorithms for Finding Agreement Supertrees.
  23. On the Closest String via Rank Distance.
  24. Simple and Efficient LZW-Compressed Multiple Pattern Matching.
  25. The Complexity of String Partitioning.
  26. An Efficient Linear Pseudo-minimization Algorithm for Aho-Corasick Automata.
  27. Computing the Burrows-Wheeler Transform of a String and Its Reverse.
  28. Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval.
  29. The Maximum Number of Squares in a Tree.
  30. Finding Longest Common Segments in Protein Structures in Nearly Linear Time.
  31. Partitioning into Colorful Components by Minimum Edge Deletions.
  32. Pattern Matching in Multiple Streams.
  33. Time-Space Trade-Offs for Longest Common Extensions.
  34. Faster and Simpler Minimal Conflicting Set Identification - (Extended Abstract).
  35. Compressed String Dictionary Look-Up with Edit Distance One.

CPM 2011

  1. Automatic Discovery of Patterns in Media Content.
  2. Faster Subsequence and Don’t-Care Pattern Matching on Compressed Texts.
  3. Edit Distance with Duplications and Contractions Revisited.
  4. Quick Greedy Computation for Minimum Common String Partitions.
  5. Forest Alignment with Affine Gaps and Anchors.
  6. Self-indexing Based on LZ77.
  7. Computational Regulatory Genomics.
  8. Unique Perfect Phylogeny Is NP-Hard.
  9. Space Lower Bounds for Online Pattern Matching.
  10. Polynomial-Time Approximation Algorithms for Weighted LCS Problem.
  11. On the Weak Prefix-Search Problem.
  12. Efficient Matching of Biological Sequences Allowing for Non-overlapping Inversions.
  13. Phylogenetic Footprinting and Consistent Sets of Local Aligments.
  14. Restricted Common Superstring and Restricted Common Supersequence.
  15. Fast Error-Tolerant Quartet Phylogeny Algorithms.
  16. Approximation Algorithms for Orienting Mixed Graphs.
  17. On Wavelet Tree Construction.
  18. Tractability Results for the Consecutive-Ones Property with Multiplicity.
  19. Frequent Submap Discovery.
  20. A Coarse-to-Fine Approach to Computing the k-Best Viterbi Paths.
  21. Efficient Seeds Computation Revisited.
  22. String Comparison and Lyndon-Like Factorization Using V-Order in Linear Time.
  23. Real-Time Streaming String-Matching.
  24. Improved MAX SNP-Hard Results for Finding an Edit Distance between Unordered Trees.
  25. Tractability and Approximability of Maximal Strip Recovery.
  26. LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations.
  27. Sparse and Truncated Suffix Trees on Variable-Length Codes.
  28. Finding Approximate and Constrained Motifs in Graphs.
  29. Simple Real-Time Constant-Space String Matching.
  30. Substring Range Reporting.
  31. Lightweight BWT Construction for Very Large String Collections.
  32. Filling Scaffolds with Gene Repetitions: Maximizing the Number of Adjacencies.
  33. Palindrome Pattern Matching.
  34. Counting Colours in Compressed Strings.
  35. Succincter Text Indexing with Wildcards.
  36. Algorithms on Grammar-Compressed Strings.
  37. Lempel-Ziv Factorization Revisited.
  38. A d-Step Approach for Distinct Squares in Strings.
  39. A Combinatorial Model of Phyllotaxis Perturbations in Arabidopsis thaliana.

CPM 2010

  1. Affine Image Matching Is Uniform TC0-Complete.
  2. Finding Optimal Alignment and Consensus of Circular Strings.
  3. Verifying a Parameterized Border Array in O(n1.5) Time.
  4. Bounds on the Minimum Mosaic of Population Sequences under Recombination.
  5. The Highest Expected Reward Decoding for HMMs with Application to Recombination Detection.
  6. Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks.
  7. Parallel and Distributed Compressed Indexes.
  8. Compression, Indexing, and Retrieval for Massive String Data.
  9. Succinct Representations of Separable Graphs.
  10. Algorithms for Forest Pattern Matching.
  11. Implicit Hitting Set Problems and Multi-genome Alignment.
  12. Breakpoint Distance and PQ-Trees.
  13. Approximate All-Pairs Suffix/Prefix Overlaps.
  14. Phylogeny- and Parsimony-Based Haplotype Inference with Constraints.
  15. Sampled Longest Common Prefix Array.
  16. The Property Suffix Tree with Dynamic Properties.
  17. Small-Space 2D Compressed Dictionary Matching.
  18. Bidirectional Search in a String with Wavelet Trees.
  19. Cover Array String Reconstruction.
  20. Succinct Dictionary Matching with No Slowdown.
  21. Extension and Faster Implementation of the GRP Transform for Lossless Compression.
  22. Optimizing Restriction Site Placement for Synthetic Genomes.
  23. Algorithms for Three Versions of the Shortest Common Superstring Problem.
  24. Extended Islands of Tractability for Parsimony Haplotyping.
  25. Pseudo-realtime Pattern Matching: Closing the Gap.
  26. Building the Minimal Automaton of A*X in Linear Time, When X Is of Bounded Cardinality.
  27. A Compact Representation of Nondeterministic (Suffix) Automata for the Bit-Parallel Approach.
  28. Mod/Resc Parsimony Inference.
  29. Old and New in Stringology.
  30. A Minimal Periods Algorithm with Applications.
  31. On the Parameterized Complexity of Some Optimization Problems Related to Multiple-Interval Graphs.

CPM 2009

  1. Permuted Longest-Common-Prefix Array.
  2. On the Value of Multiple Read/Write Streams for Data Compression.
  3. An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings.
  4. Fast RNA Structure Alignment for Crossing Input Structures.
  5. LCS Approximation via Embedding into Local Non-repetitive Strings.
  6. Linear Time Suffix Array Construction Using D-Critical Substrings.
  7. Online Approximate Matching with Non-local Distances.
  8. Fast Searching in Packed Strings.
  9. Average-Case Analysis of Perfect Sorting by Reversals.
  10. Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time.
  11. Graph Mining: Patterns, Generators and Tools.
  12. Deconstructing Intractability: A Case Study for Interval Constrained Coloring.
  13. Statistical Properties of Factor Oracles.
  14. Generalized Substring Compression.
  15. Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard.
  16. Periodic String Comparison.
  17. Haplotype Inference Constrained by Plausible Haplotype Data.
  18. Multiple Alignment of Biological Networks: A Flexible Approach.
  19. Contracted Suffix Trees: A Simple and Dynamic Text Indexing Data Structure.
  20. Efficient Inference of Haplotypes from Genotypes on a Pedigree with Mutations and Missing Alleles (Extented Abstract).
  21. Maximum Motif Problem in Vertex-Colored Graphs.
  22. Faster and Space-Optimal Edit Distance “1” Dictionary.
  23. New Complexity Bounds for Image Matching under Rotation and Scaling.
  24. CPM’s 20th Anniversary: A Statistical Retrospective.
  25. Finding All Sorting Tandem Duplication Random Loss Operations.
  26. Quasi-distinct Parsing and Optimal Compression Methods.
  27. Modeling and Algorithmic Challenges in Online Social Networks.
  28. Reoptimization of the Shortest Common Superstring Problem.
  29. Text Indexing, Suffix Sorting, and Data Compression: Common Problems and Techniques.
  30. The Structure of Level-k Phylogenetic Networks.
  31. Sparse RNA Folding: Time and Space Efficient Algorithms.

CPM 2008

  1. HP Distance Via Double Cut and Join Distance.
  2. Constrained LCS: Hardness and Approximation.
  3. An Improved Succinct Representation for Dynamic k-ary Trees.
  4. Faster Algorithm for the Set Variant of the String Barcoding Problem.
  5. Finding Largest Well-Predicted Subset of Protein Structure Models.
  6. Probabilistic Arithmetic Automata and Their Application to Pattern Matching Statistics.
  7. Two-Dimensional Pattern Matching with Combined Scaling and Rotation.
  8. Lower Bounds for Succinct Data Structures.
  9. Parameterized Algorithms and Hardness Results for Some Graph Motif Problems.
  10. Searching for Gapped Palindromes.
  11. On-Line Approximate String Matching with Bounded Errors.
  12. The Changing Face of Web Search.
  13. Computing Inverse ST in Linear Complexity.
  14. Fast Algorithms for Computing Tree LCS.
  15. Dynamic Fully-Compressed Suffix Trees.
  16. Why Greed Works for Shortest Common Superstring Problem.
  17. An(other) Entropy-Bounded Compressed Suffix Tree.
  18. Finding Additive Biclusters with Random Background.
  19. A Linear Delay Algorithm for Building Concept Lattices.
  20. Analysis of the Size of Antidictionary in.
  21. Approximate String Matching with Address Bit Errors.
  22. Fixed Parameter Tractable Alignment of RNA Structures Including Arbitrary Pseudoknots.
  23. ReCombinatorics: Combinatorial Algorithms for Studying the History of Recombination in Populations.
  24. On Compact Representations of All-Pairs-Shortest-Path-Distance Matrices.
  25. Towards a Solution to the “Runs” Conjecture.
  26. A Black Box for Online Approximate Pattern Matching.
  27. Matching Integer Intervals by Minimal Sets of Binary Words with don’t cares.
  28. On the Longest Common Parameterized Subsequence.

CPM 2007

  1. Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions.
  2. Fast and Practical Algorithms for Computing All the Runs in a String.
  3. On Demand String Sorting over Unbounded Alphabets.
  4. Processing Compressed Texts: A Tractability Border.
  5. Self-normalised Distance with Don’t Cares.
  6. Most Burrows-Wheeler Based Compressors Are Not Optimal.
  7. Computing Exact p-Value for Structured Motif.
  8. Move-to-Front, Distance Coding, and Inversion Frequencies Revisited.
  9. Longest Common Separable Pattern Among Permutations.
  10. A Simple Construction of Two-Dimensional Suffix Trees in Linear Time.
  11. Common Structured Patterns in Linear Graphs: Approximation and Combinatorics.
  12. A New and Faster Method of Sorting by Transpositions.
  13. Algorithms for Computing the Longest Parameterized Common Subsequence.
  14. Improved Algorithms for Inferring the Minimum Mosaic of a Set of Recombinants.
  15. Cache-Oblivious Index for Approximate String Matching.
  16. Fixed-Parameter Tractability of the Maximum Agreement Supertree Problem.
  17. Finding Compact Structural Motifs.
  18. Tiling Periodicity.
  19. A Lempel-Ziv Text Index on Secondary Storage.
  20. Dynamic Rank-Select Structures with Applications to Run-Length Encoded Texts.
  21. Finding Witnesses by Peeling.
  22. Improved Sketching of Hamming Distance with Error Correcting.
  23. A Combinatorial Approach to Genome-Wide Ortholog Assignment: Beyond Sequence Similarity Search.
  24. Deterministic Length Reduction: Fast Convolution in Sparse Data and Applications.
  25. Algorithmic Problems in Scheduling Jobs on Variable-Speed Processors.
  26. Suffix Arrays on Words.
  27. Space-Efficient Algorithms for Document Retrieval.
  28. Identification of Distinguishing Motifs.
  29. Efficient Computation of Substring Equivalence Classes with Suffix Arrays.
  30. Guided Forest Edit Distance: Better Structure Comparisons by Using Domain-knowledge.
  31. Compressed Text Indexes with Fast Locate.
  32. Stringology: Some Classic and Some Modern Problems.
  33. Improved Approximate String Matching and Regular Expression Matching on Ziv-Lempel Compressed Texts.
  34. Non-breaking Similarity of Genomes with Gene Repetitions.
  35. Two-Dimensional Range Minimum Queries.

CPM 2006

  1. Common Substrings in Random Strings.
  2. SNP and Haplotype Analysis - Algorithms and Applications.
  3. Property Matching and Weighted Matching.
  4. Faster Algorithms for Computing Longest Common Increasing Subsequences.
  5. Subsequence Combinatorics and Applications to Microarray Production, DNA Sequencing and Chaining Algorithms.
  6. Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE.
  7. Obtaining Provably Good Performance from Suffix Trees in Secondary Storage.
  8. Approximation of RNA Multiple Structural Alignment.
  9. An Improved Algorithm for the Macro-evolutionary Phylogeny Problem.
  10. An O(n3/2sqrt(log n)) Algorithm for Sorting by Reciprocal Translocations.
  11. Reducing the Space Requirement of LZ-Index.
  12. On-Line Linear-Time Construction of Word Suffix Trees.
  13. Geometric Suffix Tree: A New Index Structure for Protein 3-D Structures.
  14. A Linear Size Index for Approximate Pattern Matching.
  15. Sublinear Algorithms for Parameterized Matching.
  16. Statistical Encoding of Succinct Data Structures.
  17. New Bounds for Motif Finding in Strong Instances.
  18. Large Scale Matching for Position Weight Matrices.
  19. Solving the Maximum Agreement SubTree and the Maximum Compatible Tree Problems on Many Bounded Degree Trees.
  20. Tiling an Interval of the Discrete Line.
  21. Adaptive Searching in Succinctly Encoded Binary Relations and Tree-Structured Documents.
  22. Identifying Co-referential Names Across Large Corpora.
  23. Dynamic Entropy-Compressed Sequences and Full-Text Indexes.
  24. New Algorithms for Text Fingerprinting.
  25. Approximate Matching in Weighted Sequences.
  26. Asynchronous Pattern Matching.
  27. Finding Common RNA Pseudoknot Structures in Polynomial Time.
  28. On the Repeat-Annotated Phylogenetic Tree Reconstruction Problem.
  29. Fingerprint Clustering with Bounded Number of Missing Values.
  30. Algorithms for Finding a Most Similar Subforest.
  31. A Simpler Analysis of Burrows-Wheeler Based Compression.
  32. Local Alignment of RNA Sequences with Arbitrary Scoring Schemes.
  33. Faster Two Dimensional Scaled Matching.
  34. Efficient Algorithms for Regular Expression Constrained Sequence Alignment.
  35. A Compact Mathematical Programming Formulation for DNA Motif Finding.
  36. Longest Common Subsequences in Permutations and Maximum Cliques in Circle Graphs.

CPM 2005

  1. Hardness of Optimal Spaced Seed Design.
  2. The Median Problem for the Reversal Distance in Circular Bacterial Genomes.
  3. Weighted Directed Word Graph.
  4. Parametric Analysis for Ungapped Markov Models of Evolution.
  5. An Extension of the Burrows Wheeler Transform and Applications to Sequence Comparison and Data Compression.
  6. Mass Spectra Alignments and Their Significance.
  7. A Polynomial Time Matching Algorithm of Ordered Tree Patterns Having Height-Constrained Variables.
  8. Speeding up Parsing of Biological Context-Free Grammars.
  9. Incremental Inference of Relational Motifs with a Degenerate Alphabet.
  10. Linear-Time Construction of Compressed Suffix Arrays Using o(n log n)-Bit Working Space for Large Alphabets.
  11. Exact and Approximation Algorithms for DNA Tag Set Design.
  12. A New Compressed Suffix Tree Supporting Fast Search and Its Construction Algorithm Using Optimal Working Space.
  13. A Simple Fast Hybrid Pattern-Matching Algorithm.
  14. A Fast Algorithm for Approximate String Matching on Gene Sequences.
  15. On the Complexity of Sparse Exon Assembly.
  16. Sharper Upper and Lower Bounds for an Approximation Scheme for Consensus-Pattern.
  17. Faster Algorithms for delta, gamma-Matching and Related Problems.
  18. Regular Expression Constrained Sequence Alignment.
  19. An Upper Bound on the Hardness of Exact Matrix Based Motif Discovery.
  20. Reducing the Size of NFAs by Using Equivalences and Preorders.
  21. Two Dimensional Parameterized Matching.
  22. Text Indexing with Errors.
  23. Linear Programming for Phylogenetic Reconstruction Based on Gene Rearrangements.
  24. Construction of Aho Corasick Automaton in Linear Time for Integer Alphabets.
  25. Approximate Matching in the L1 Metric.
  26. A New Periodicity Lemma.
  27. An Efficient Algorithm for Generating Super Condensed Neighborhoods.
  28. Inferring a Graph from Path Frequency.
  29. Identifying Similar Surface Patches on Proteins Using a Spin-Image Surface Representation.
  30. Prefix-Free Regular-Expression Matching.
  31. An Optimal Algorithm for Online Square Detection.
  32. Assessing the Significance of Sets of Words.
  33. DNA Compression Challenge Revisited: A Dynamic Programming Approach.
  34. A Linear Tree Edit Distance Algorithm for Similar Ordered Trees.
  35. On the Longest Common Rigid Subsequence Problem.
  36. Succinct Suffix Arrays Based on Run-Length Encoding.
  37. Using PQ Trees for Comparative Genomics.

CPM 2004

  1. Two Algorithms for LCS Consecutive Suffix Alignment.
  2. Sorting by Length-Weighted Reversals: Dealing with Signs and Circularity.
  3. Faster Two Dimensional Pattern Matching with Rotations.
  4. Computational Design of New and Recombinant Selenoproteins.
  5. Maximal Common Connected Sets of Interval Graphs.
  6. A Fast Set Intersection Algorithm for Sorted Sequences.
  7. Reversal Distance without Hurdles and Fortresses.
  8. Sparse Normalized Local Alignment.
  9. Real-Time String Matching in Sublinear Space.
  10. Approximate Point Set Pattern Matching on Sequences and Planes.
  11. Average-Case Analysis of Approximate Trie Search (Extended Abstract).
  12. Compressed Index for a Dynamic Collection of Texts.
  13. A Computational Model for RNA Multiple Structural Alignment..
  14. The Protein Sequence Design Problem in Canonical Model on 2D and 3D Lattices.
  15. Performing Local Similarity Searches with Variable Length Seeds.
  16. On the Average Sequence Complexity.
  17. Quadratic Time Algorithms for Finding Common Intervals in Two and More Sequences.
  18. Approximate String Matching Using Compressed Suffix Arrays.
  19. Small Phylogeny Problem: Character Evolution Trees.
  20. A Simple Optimal Representation for Balanced Parentheses.
  21. New Results for the 2-Interval Pattern Problem.
  22. Sorting by Reversals in Subquadratic Time.
  23. A Trie-Based Approach for Compacting Automata.
  24. Maximum Agreement and Compatible Supertrees (Extended Abstract).
  25. On the k-Closest Substring and k-Consensus Pattern Problems.
  26. Polynomial-Time Algorithms for the Ordered Maximum Agreement Subtree Problem.
  27. A Linear-Time Algorithm for Computing Translocation Distance between Signed Genomes.
  28. Finding Biclusters by Random Projections.
  29. Efficient Algorithms for Finding Submasses in Weighted Strings.
  30. Computational Problems in Perfect Phylogeny Haplotyping: Xor-Genotypes and Tag SNPs.
  31. Optimizing Multiple Spaced Seeds for Homology Search.
  32. Compressed Compact Suffix Arrays.
  33. Improved Single and Multiple Approximate String Matching.
  34. Approximate Labelled Subtree Homeomorphism.
  35. Multi-seed Lossless Filtration (Extended Abstract).
  36. A Combinatorial Shape Matching Algorithm for Rigid Protein Docking.

CPM 2003

  1. Space Efficient Linear Time Construction of Suffix Arrays.
  2. Constrained Tree Inclusion.
  3. Haplotype Inference by Pure Parsimony.
  4. Average-Optimal Multiple Approximate String Matching.
  5. Working on the Problem of Sorting by Transpositions on Genome Rearrangements.
  6. An Effective Algorithm for the Peptide De Novo Sequencing from MS/MS Spectrum.
  7. Optimal Spaced Seeds for Hidden Markov Models, with Application to Homologous Coding Regions.
  8. A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions.
  9. An Exact and Polynomial Distance-Based Algorithm to Reconstruct Single Copy Tandem Duplication Trees.
  10. Two-Dimensional Pattern Matching with Rotations.
  11. Alignment between Two Multiple Alignments.
  12. Sparse LCS Common Substring Alignment.
  13. Efficient Selection of Unique and Popular Oligos for Large EST Databases.
  14. Pattern Discovery in RNA Secondary Structure Using Affix Trees.
  15. A Fully Linear-Time Approximation Algorithm for Grammar-Based Compression.
  16. Analysis of Tree Edit Distance Algorithms.
  17. Extracting Approximate Patterns.
  18. Fast Lightweight Suffix Array Construction and Checking.
  19. Complexities of the Centre and Median String Problems.
  20. Tuning String Matching for Huge Pattern Sets.
  21. Linear-Time Construction of Suffix Arrays.
  22. Distributed and Paged Suffix Trees for Large Genetic Databases.
  23. Optimal Partitions of Strings: A New Class of Burrows-Wheeler Compression Algorithms.
  24. An Improved Algorithm for Generalized Comparison of Minisatellites.
  25. Multiple Genome Alignment: Chaining Algorithms Revisited.
  26. On Minimizing Pattern Splitting in Multi-track String Matching.
  27. More Efficient Left-to-Right Pattern Matching in Non-sequential Equational Programs.
  28. Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations by Reversals.

CPM 2002

  1. Two-Pattern Strings.
  2. Pattern Matching Problems over 2-Interval Sets.
  3. Block Merging for Off-Line Compression.
  4. Local Similarity Based Point-Pattern Matching.
  5. On the Complexity of Deriving Position Specific Score Matrices from Examples.
  6. Identifying Occurrences of Maximal Pairs in Multiple Strings.
  7. Application of Lempel-Ziv Factorization to the Approximation of Grammar-Based Compression.
  8. Practical Software for Aligning ESTs to Human Genome.
  9. Space-Economical Algorithms for Finding Maximal Unique Matches.
  10. One-Gapped q-Gram Filtersfor Levenshtein Distance.
  11. Faster Bit-Parallel Approximate String Matching.
  12. Simple and Practical Sequence Nearest Neighbors with Block Operations.
  13. The Problem of Context Sensitive String Matching.
  14. Towards Optimally Solving the LONGEST COMMON SUBSEQUENCE Problem for Sequences with Nested Arc Annotations in Linear Time.
  15. Optimal Exact and Fast Approximate Two Dimensional Pattern Matching Allowing Rotations.
  16. Efficient Text Mining with Optimized Pattern Discovery.
  17. Edit Distance with Move Operations.
  18. Statistical Identification of Uniformly Mutated Segments within Repeats.
  19. Constructing NFA s by Optimal Use of Positions in Regular Expressions.
  20. A Better Method for Length Distribution Modeling in HMMs and Its Application to Gene Finding.
  21. Three Heuristics for delta-Matching: delta-BM Algorithms.
  22. The Minimum DAWG for All Suffixes of a String and Its Applications.
  23. String Matching with Stopper Encoding and Code Splitting.

CPM 2001

  1. Regular Expression Searching over Ziv-Lempel Compressed Text.
  2. Efficient Discovery of Proximity Patterns with Suffix Arrays.
  3. Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its Applications.
  4. A Very Elementary Presentation of the Hannenhalli-Pevzner Theory.
  5. Optimally Compact Finite Sphere Packings - Hydrophobic Cores in the FCC.
  6. Approximate Matching of Run-Length Compressed Strings.
  7. An Output-Sensitive Flexible Pattern Discovery Algorithm.
  8. String Resemblance Systems: A Unifying Framework for String Similarity with Applications to Literature and Music.
  9. Balanced Suffix Trees (Invited Lecture).
  10. Computing the Equation Automaton of a Regular Expression in Space and Time.
  11. Tandem Cyclic Alignment.
  12. Finding All Common Intervals of k Permutations.
  13. Minimum Quartet Inconsistency Is Fixed Parameter Tractable.
  14. Multiple Pattern Matching Algorithms on Collage System.
  15. Parallel Lempel Ziv Coding.
  16. On-Line Construction of Compact Directed Acyclic Word Graphs.
  17. An Extension of the Periodicity Lemma to Longer Periods (Invited Lecture).
  18. Fuzzy Hamming Distance: A New Dissimilarity Measure.
  19. Efficient Experimental String Matching by Weak Factor Recognition.
  20. Better Filtering with Gapped q-Grams.
  21. A Fast Algorithm for Optimal Alignment between Similar Ordered Trees.
  22. Episode Matching.
  23. What to Do with All this Hardware? (Invited Lecture).
  24. Generalized Pattern Matching and the Complexity of Unavoidability Testing.

CPM 2000

  1. Approximate String Matching over Ziv-Lempel Compressed Text.
  2. Parametric Multiple Sequence Alignment and Phylogeny Construction.
  3. Shift Error Detection in Standardized Exams.
  4. A Faster and Unifying Algorithm for Comparing Trees.
  5. Compact Suffix Array.
  6. Structural Properties and Tractability Results for Linear Synteny.
  7. Genome Rearrangement by Reversals and Insertions/Deletions of Contiguous Segments.
  8. Indexing Text with Approximate q-Grams.
  9. Exact and Efficient Computation of the Expected Number of Missing and Common Words in Random Texts.
  10. The Combinatorial Partitioning Method.
  11. Boyer-Moore String Matching over Ziv-Lempel Compressed Text.
  12. Approximating the Maximum Isomorphic Agreement Subtree Is Hard.
  13. Explaining and Controlling Ambiguity in Dynamic Programming.
  14. Tsukuba BB: A Branch and Bound Algorithm for Local Multiple Sequence Alignment.
  15. Identifying and Filtering Near-Duplicate Documents.
  16. The Longest Common Subsequence Problem for Arc-Annotated Sequences.
  17. Finding Maximal Quasiperiodicities in Strings.
  18. An Upper Bound for Number of Contacts in the HP-Model on the Face-Centered-Cubic Lattice (FCC).
  19. A Polynominal Time Approximation Scheme for the Closest Substring Problem.
  20. Improving Static Compression Schemes by Alphabet Extension.
  21. A Boyer-Moore Type Algorithm for Compressed Pattern Matching.
  22. Approximation Algorithms for Hamming Clustering Problems.
  23. Machine Learning for Efficient Natural-Language Processing.
  24. Linear Bidirectional On-Line Construction of Affix Trees.
  25. Browsing around a Digital Library: Today and Tomorrow.
  26. Incomplete Directed Perfect Phylogeny.
  27. Simple Optimal String Matching Algorithm.
  28. Using Suffix Trees for Gapped Motif Discovery.
  29. Algorithmic Aspects of Speech Recognition: A Synopsis.
  30. Some Results on Flexible-Pattern Discovery.
  31. A Dynamic Edit Distance Table.
  32. Periods and Quasiperiods Characterization.
  33. A Lower Bound for the Breakpoint Phylogeny Problem.
  34. On the Complexity of Determining the Period of a String.

CPM 1999

  1. Pattern Matching in Text Compressed by Using Antidictionaries.
  2. A General Practical Approach to Pattern Matching over Ziv-Lempel Compressed Text.
  3. Physical Mapping with Repeated Probes: The Hypergraph Superstring Problem.
  4. Finding Common Subsequences with Arcs and Pseudoknots.
  5. Applying an Edit Distance to the Matching of Tree Ring Sequences in Dendrochronology.
  6. Approximate Periods of Strings.
  7. GESTALT: Genomic Steiner Alignments.
  8. On the Structure of Syntenic Distance.
  9. A Dynamic Data Structure for Reverse Lexicographically Sorted Prefixes.
  10. Computing Similarity between RNA Structures.
  11. On the Complexity of Positional Sequencing by Hybridization.
  12. Finding Common RNA Secondary Structures from RNA Sequences.
  13. Bounds on the Number of String Subsequences.
  14. Hybridization and Genome Rearrangement.
  15. Shift-And Approach to Pattern Matching in LZW Compressed Text.
  16. Matching of Spots in 2D Electrophoresis Images. Point Matching Under Non-uniform Distortions.
  17. Ziv Lempel Compression of Huge Natural Language Data Tries Using Suffix Arrays.
  18. Finding Maximal Pairs with Bounded Gap.
  19. Fast Multi-dimensional Approximate Pattern Matching.
  20. A New Indexing Method for Approximate String Matching.
  21. The Compression of Subsegments of Images Described by Finite Automata.

CPM 1998

  1. Comparison of Coding DNA.
  2. Approximate Word Sequence Matching over Sparse Suffix Trees.
  3. A Rotation Invariant Filter for Two-Dimensional String Matching.
  4. Genome Halving.
  5. A Fast Bit-Vector Algorithm for Approximate String Matching Based on Dynamic Programming.
  6. An Approximate Oracle for Distance in Metric Spaces.
  7. Efficient Special Cases of Pattern Matching with Swaps.
  8. Reporting Exact and Approximate Regular Expression Matches.
  9. Constructing Suffix Arrays for Multi-dimensional Matrices.
  10. Aligning Alignments.
  11. A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching.
  12. Efficient Parallel Algorithm for the Editing Distance between Ordered Trees.
  13. A Very Fast String Matching Algorithm for Small Alphabeths and Long Patterns (Extended Abstract).
  14. Fixed Topology Alignment with Recombination.
  15. Simple and Flexible Detection of Contiguous Repeats Using a Suffix Tree (Preliminary Version).
  16. Aligning DNA Sequences to Minimize the Change in Protein (Extended Abstract).
  17. A Dictionary Matching Algorithm Fast on the Average for Terms of Varying Length.

CPM 1997

  1. On the Nadeau-Taylor Theory of Conserved Chromosome Segments.
  2. Approximation Algorithms for the Fixed-Topology Phylogenetic Number Problem.
  3. Aligning Coding DNA in the Presence of Frame-Shift Errors.
  4. Episode Matching.
  5. A New Algorithm for the Ordered Tree Inclusion Problem.
  6. A Filter Method for the Weighted Local Similarity Search Problem.
  7. Flexible Identification of Structural Objects in Nucleic Acid Sequences: Palindromes, Mirror Repeats, Pseudoknots and Triple Helices.
  8. Space- and Time-Efficient Decoding with Canonical Huffman Trees.
  9. On Incremental Computation of Transitive Closure and Greedy Alignment.
  10. External Inverse Pattern Matching.
  11. Direct Construction of Compact Directed Acyclic Word Graphs.
  12. An Improved Pattern Matching Algorithm for Strings in Terms of Straight-Line Programs.
  13. Distributed Generation of Suffix Arrays.
  14. Trie-Based Data Structures for Sequence Assembly.
  15. Iterative versus simultaneous Multiple Sequence Alignment (Abstract).
  16. Efficient Algorithms for Approximate String Matching with Swaps (Extended Abstract).
  17. Estimating the Probability of Approximate Matches.
  18. Banishing Bias from Consensus Sequences.
  19. On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts.
  20. Modern Comparative Lexicostatistics.
  21. An Easy Case of Sorting by Reversals.
  22. On Weak Circular Squares in Binary Words.

CPM 1996

  1. Analysis of Two-Dimensional Approximate Pattern Matching Algorithms.
  2. Docking of Conformationally Flexible Proteins.
  3. Improved Approximation Algorithms for Tree Alignment.
  4. Spliced Alignment: A New Approach to Gene Recognition.
  5. Perfect Hashing for Strings: Formalization and Algorithms.
  6. Original Synteny.
  7. Suffix Trees on Words.
  8. Boyer-Moore Strategy to Efficient Approximate String Matching.
  9. Invariant Patterns in Crystal Lattices: Implications for Protein Folding Algorithms (Extended Abstract).
  10. Filtration with q-Samples in Approximate String Matching.
  11. Approximate Multiple Strings Search.
  12. Approximation Algorithms for Maximum Two-Dimensional Pattern Matching.
  13. Efficient Parallel Algorithms for Tree Editing Problems.
  14. Poisson Process Approximation for Repeats in One Sequence and Its Application to Sequencing by Hybridization.
  15. Approximate Dictionary Queries.
  16. Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract).
  17. Approximate Pattern Matching in Directed Graphs.
  18. Computing Discoveries in Molecular Biology (Abstract).
  19. Finite-State Computability of Annotations of Strings and Trees.
  20. A Double Combinatorial Approach to Discovering Patterns in Biological Sequences.
  21. A Faster Algorithm for Approximate String Matching.
  22. Constructing Computer Virus Phylogenies.
  23. Graph Traversals, Genes, and Matroids: An Efficient Case of the Travelling Salesman Problem.
  24. Fast Sorting by Reversal.
  25. The Asymmetric Median Tree - A New model for Building Consensus Trees.
  26. The suffix Tree of a Tree and Minimizing Sequential Transducers.
  27. Alphabet Independent and Dictionary Scaled Matching.
  28. A 2 2/3-Approximation Algorithm for the Shortest Superstring Problem.

CPM 1995

  1. Of Chicken Teeth and Mouse Eyes, or Generalized Character Compatibility.
  2. Pairwise Alignment with Scoring on Tuples.
  3. Pattern Matching in Directed Graphs.
  4. Approximation Algorithms for Multiple Sequence Alignment Under a Fixed Evolutionary Tree.
  5. Multi-Dimensional Pattern Matching with Dimensional Wildcards.
  6. Fast Approximate Matching using Suffix Trees.
  7. Making the Shortest-Paths Approach to Sum-of-Pairs Multiple Sequence Alignment More Space Efficient in Practice (Extended Abstract).
  8. String Matching in Hypertext.
  9. New Results and Open Problems Related to Non-Standard Stringology.
  10. Constant-Space String Matching with Smaller Number of Comparisons: Sequential Sampling.
  11. Dictionary Loop-Up with Small Errors.
  12. Pattern-Matching for Strings with Short Descriptions.
  13. Polynomial-time Algorithm for Computing Translocation Distance between Genomes.
  14. Minimizing Phylogenetic Number to find Good Evolutionary Trees.
  15. Computing Similarity between RNA Strings.
  16. Multiple Sequence Comparison: A Peptide Matching Approach.
  17. Genome Analysis: Pattern Search in Biological Macromolecules.
  18. A New Flexible Algorithm for the Longest Common Subsequence Problem.
  19. Three-Dimensional Pattern Matching in Protein Structure Analysis.
  20. Efficient String Matching on Coded Texts.
  21. Common Subsequences and Supersequences and Their expected Length.
  22. Matching Patterns of An Automaton.
  23. Smaller Representations for Finite-State Transducers and Finite-State Automata.
  24. Suffix Cactus: A Cross between Suffix Tree and Suffix Array.
  25. On a Technique for Parsing a String (Abstract).
  26. An Efficient Algorithm for Developing Topological Valid Matchings.
  27. On the Complexity of Comparing Evolutionary Trees (Extended Abstract).
  28. On the Editing Distance between Undirected Acyclic Graphs and Related Problems.
  29. Matching a Set of Strings with Variable Length Don’t Cares.

CPM 1994

  1. Matching with Matrix Norm Minimization.
  2. Recent Methods for RNA Modeling Using Stochastic Context-Free Grammars.
  3. A Context Dependent Method for Comparing Sequences.
  4. A Text Compression Scheme That Allows Fast Searching Directly in the Compressed File.
  5. Maximal Common Subsequences and Minimal Common Supersequences.
  6. Dictionary-Matching on Unbounded Alphabets: Uniform Length Dictionaries.
  7. A Lossy Data Compression Based on String Matching: Preliminary Analysis and Suboptimal Algorithms.
  8. Multiple Matching of Parameterized Patterns.
  9. Alignment of Trees - An Alternative to Tree Edit.
  10. The Parameterized Complexity of Sequence Alignment and Consensus.
  11. Approximate String Matching and Local Similarity.
  12. Approximation Algorithms for Multiple Sequence Alignment.
  13. Proximity Matching Using Fixed-Queries Trees.
  14. A Space Efficient Algorithm for Finding the Best Non-Overlapping Alignment Score.
  15. An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern.
  16. Computing all Suboptimal Alignments in Linear Space.
  17. Unit Route Upper Bound for String-Matching on Hypercube.
  18. Polynomial-Time Algorithms for Computing Characteristic Strings.
  19. Fast Identification of Approximately Matching Substrings.
  20. Computation of Squares in a String (Preliminary Version).
  21. Minimization of Sequential Transducers.
  22. Shortest Common Superstrings for Strings of Random Letters.
  23. Approximate String Matching with Don’t Care Characters.
  24. Parametric Recomuting in Alignment Graphs.
  25. Query Primitives for Tree-Structured Data.
  26. Efficient Bounds for Oriented Chromosome Inversion Distance.

CPM 1993

  1. A Linear Time Pattern Matching Algorithm Between a String and a Tree.
  2. An Algorithm for Approximate Tandem Repeats.
  3. A Unifying Look at d-Dimensional Periodicities and Space Coverings.
  4. Two Dimensional Pattern Matching in a Digitized Image.
  5. Minimal Separators of Two Words.
  6. Tight Comparison Bounds for the String Prefix-Matching Problem.
  7. Detecting False Matches in String Matching Algorithms.
  8. Analysis of a String Edit Problem in a Probabilistic Framework (Extended Abstract).
  9. Approximate String-Matching over Suffix Trees.
  10. The Maximum Weight Trace Problem in Multiple Sequence Alignment.
  11. Covering a String.
  12. Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes.
  13. A Fast Filtration Algorithm for the Substring Matching Problem.
  14. A New Editing based Distance between Unordered Labeled Trees.
  15. On the Worst-Case Behaviour of Some Approximation Algorithms for the Shortest Common Supersequence of k Strings.
  16. An Algorithm for Locating Non-Overlapping Regions of Maximum Alignment Score.
  17. On Suboptimal Alignments of Biological Sequences.
  18. 3-D Docking of Protein Molecules.
  19. Multiple Sequence Comparison and n-Dimensional Image Reconstruction.

CPM 1992

  1. 3-D Substructure Matching in Protein Molecules.
  2. Theoretical and Empirical Comparisons of Approximate String Matching Algorithms.
  3. Computing Display Conflicts in String and Circular String Visualization.
  4. DZ: A Text Compression Algorithm For Natural Languages.
  5. Fast Serial and Parallel Algorithms for Approximate Tree Matching with VLDC’s.
  6. Matrix Longest Common Subsequence Problem, Duality and Hibert Bases.
  7. Fast and Practical Approximate String Matching.
  8. Color Set Size Problem with Application to String Matching.
  9. Multiple Alignment with Guaranteed Error Bounds and Communication Cost.
  10. Pattern Matching With Mismatches: A Probabilistic Analysis and a Randomized Algorithm (Extended Abstract).
  11. Heaviest Increasing/Common Subsequence Problems.
  12. Probabilistic Analysis of Generalized Suffix Trees (Extended Abstract).
  13. Identifying Periodic Occurrences of a Template with Applications to Protein Structures.
  14. A Language Approach to String Searching Evaluation.
  15. Dynamic Dictionary Matching with Failure Functions (Extended Abstract).
  16. Grammatical Tree Matching.
  17. From Regular Expressions to DFA’s Using Compressed NFA’s.
  18. Edit Distances for Genome Comparisons Based on Non-Local Operations.
  19. Efficient Randomized Dictionary Matching Algorithms (Extended Abstract).
  20. Two Algorithms for the Longest Common Subsequence of Three (or More) Strings.
  21. Approximate Regular Expression Pattern Matching with Concave Gap Penalties.
  22. Fast Multiple Keyword Searching.
This site is open source. Improve this page.