Combinatorial Pattern Matching: 26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings (Lecture Notes in Computer Science Book 9133)

This book constitutes the refereed proceedings of the 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015, held on Ischia Island, Italy, in June/July 2015. The 34 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 83 submissions. The papers address issues of searching and matching strings and more complicated patterns such as trees; regular expressions; graphs; point sets; and arrays. The goal is to derive combinatorial properties of such structures and to exploit these properties in order to achieve superior performance for the corresponding computational problems. The meeting also deals with problems in computational biology; data compression and data mining; coding; information retrieval; natural language processing; and pattern recognition. Front Matter....Pages I-XIX On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling....Pages 1-12 A Framework for Space-Efficient String Kernels....Pages 13-25 Composite Repetition-Aware Data Structures....Pages 26-39 Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis....Pages 40-51 Longest Common Extensions in Trees....Pages 52-64 Longest Common Extensions in Sublinear Space....Pages 65-76 Ranked Document Retrieval with Forbidden Pattern....Pages 77-88 Parameterized Complexity of Superstring Problems....Pages 89-99 On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem....Pages 100-113 Fast String Dictionary Lookup with One Error....Pages 114-123 On the Readability of Overlap Digraphs....Pages 124-137 Improved Algorithms for the Boxed-Mesh Permutation Pattern Matching Problem....Pages 138-148 Range Minimum Query Indexes in Higher Dimensions....Pages 149-159 Alphabet-Dependent String Searching with Wexponential Search Trees....Pages 160-171 Lempel Ziv Computation in Small Space (LZ-CISS)....Pages 172-184 Succinct Non-overlapping Indexing....Pages 185-195 Encodings of Range Maximum-Sum Segment Queries and Applications....Pages 196-206 Combinatorial RNA Design: Designability and Structure-Approximating Algorithm....Pages 207-218 Dictionary Matching with Uneven Gaps....Pages 219-230 Partition into Heapable Sequences, Heap Tableaux and a Multiset Extension of Hammersley’s Process....Pages 231-246 The Approximability of Maximum Rooted Triplets Consistency with Fan Triplets and Forbidden Triplets....Pages 247-260 String Powers in Trees....Pages 261-271 Online Detection of Repetitions with Backtracking....Pages 272-283 Greedy Conjecture for Strings of Length 4....Pages 284-294 Tighter Bounds for the Sum of Irreducible LCP Values....Pages 295-306 Parallel External Memory Suffix Sorting....Pages 307-315 On Maximal Unbordered Factors....Pages 316-328 Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree....Pages 329-342 Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints....Pages 343-354 A Probabilistic Analysis of the Reduction Ratio in the Suffix-Array IS-Algorithm....Pages 355-366 Encoding Nearest Larger Values....Pages 367-373 Sorting by Cuts, Joins and Whole Chromosome Duplications....Pages 374-384 Back Matter....Pages 385-395 ....Pages 396-409