Titlebook: Combinatorial Pattern Matching; 26th Annual Symposiu Ferdinando Cicalese,Ely Porat,Ugo Vaccaro Conference proceedings 2015 Springer Interna

BOOR

跳动

A Framework for Space-Efficient String Kernels, time per element in its output. The same bounds hold for a number of measures of compositional complexity based on multiple values of ., like the .-mer profile and the .-th order empirical entropy, and for calibrating the value of . using the data.

高深莫测

Efficient Construction of a Compressed de Bruijn Graph for Pan-Genome Analysis,r algorithm has a better worst-case time complexity of ., where . is the size of the alphabet (. for DNA). Moreover, experiments show that it is much faster than splitMEM while using only a fraction of the space required by splitMEM.

Ordeal

Succinct Non-overlapping Indexing,uffix range of . in . time, and (ii) a suffix array or an inverse suffix array value in . time; then by using . alone, we can answer a query . in . time. Additionally, we present an improved result for a generalized version of this problem called ..

Eulogy

Composite Repetition-Aware Data Structures, the number of extensions of maximal repeats. The combination of CDAWG and RLBWT enables also a new representation of the suffix tree, whose size depends again on the number of extensions of maximal repeats, and that is powerful enough to support matching statistics and constant-space traversal.

olfction

Longest Common Extensions in Trees,ng that any path-tree LCE structure of size . must necessarily use . time to answer queries. For . queries, we present a time-space trade-off, that given any parameter ., ., leads to an . space and . query-time solution. This is complemented with a reduction to the set intersection problem implying

HAIL

监禁

脊椎动物

Range Minimum Query Indexes in Higher Dimensions, of designing indexing data structures for RMQs in higher dimensions. We design a data structure of size .. that supports RMQs in constant time for a constant number of dimensions. We also show how to obtain trade-offs between the space of indexing data structures and their query time.

撕裂皮肉