Titlebook: String Processing and Information Retrieval; 30th International S Franco Maria Nardini,Nadia Pisanti,Rossano Venturi Conference proceedings

CARE

,Approximation and Fixed Parameter Algorithms for the Approximate Cover Problem,combinatorics. A . of a string . is a string . for which every letter of . lies within some occurrence of .. The input of the . consists of a string . and the goal is to find a string . of length less than the length of . that covers a string ., which is as close to . as possible (under some predefi

临时抱佛脚

,Data Structures for SMEM-Finding in the PBWT,on of the divergence array. Although run-length encoding the PBWT has been previously considered, storing the divergence array along with the PBWT in a compressed manner has not been as rigorously studied. We define two queries that can be used in combination to compute SMEMs, allowing us to define

Brocas-Area

,Compressibility Measures for Two-Dimensional Data,e smallest string attractor, and the . measure defined in terms of the number of distinct substrings of the input string. Concretely, we introduce the two-dimensional measures . and . as natural generalizations of . and . and study some of their properties. Among other things, we prove that . is mon

变白

,From de Bruijn Graphs to Variation Graphs – Relationships Between Pangenome Models,nalities, applications provided by available tools, their efficiency etc. Among them, two graph-based models are particularly widely used: variation graphs and de Bruijn graphs..In the current paper we propose an axiomatization of the desirable properties of a graph representation of a collection of

stroke

arrhythmic

延期

,Computing All-vs-All MEMs in Grammar-Compressed Text,ur work is the construction of a fully-balanced grammar . from . that meets a property that we call .: the expansions of the nonterminals that have the same height in the parse tree form a fix-free set (i.e., prefix-free and suffix-free). The fix-free property allows us to compute the MEMs of . incr

率直

Sublinear Time Lempel-Ziv (LZ77) Factorization,ngth-. string over integer alphabet . with ., and on a word RAM of width ., it can be computed in . time. However, the packed representation of the string occupies only . bits or equivalently . words of space, and hence we can hope for algorithms that run in . time and words of space. Kempa showed h

薄荷醇

,New Advances in Rightmost Lempel-Ziv,-. string over a linearly-sortable alphabet, e.g., . with ., it can be computed in . time. It is unknown whether this time can be achieved for the . LZ parsing, where each referencing phrase points to its rightmost previous occurrence. The currently best solution takes . time (Belazzougui & Puglisi

CAJ

,Engineering a Textbook Approach to Index Massive String Dictionaries,es of strings..Our solution is based on a very simple approach that consists of decoupling string storage and string indexing by means of a blockwise compression of the sorted dictionary strings (to be stored in external memory) and a succinct implementation of a Patricia trie (to be stored in inter