Artículo de revista
Document listing on repetitive collections with guaranteed performance
Leibniz International Proceedings in Informatics, LIPIcs, Volumen 78,
We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of size N over alphabet [1, σ] is composed of D copies of a string of size n, and s single-character edits are applied on the copies. We introduce the first document listing index with size Õ(n+s), precisely O((n lg σ+s lg2 N) lg D) bits, and with useful worst-case time guarantees: Given a pattern of length m, the index reports the ndoc strings where it appears in time O(m2 + m lg N(lgD + lgϵ N).