2026-08-11T18:45:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8700 2024-03-06T10:43:00Z ddc:004 open_access

Non-Overlapping Indexing - Cache Obliviously Hooshmand, Sahar Abedin, Paniz Külekci, M. Oguzhan Thankachan, Sharma V. Suffix Trees Cache Oblivious Data Structure String Algorithms The non-overlapping indexing problem is defined as follows: pre-process a given text T[1,n] of length n into a data structure such that whenever a pattern P[1,p] comes as an input, we can efficiently report the largest set of non-overlapping occurrences of P in T. The best known solution is by Cohen and Porat [ISAAC, 2009]. Their index size is O(n) words and query time is optimal O(p+nocc), where nocc is the output size. We study this problem in the cache-oblivious model and present a new data structure of size O(n log n) words. It can answer queries in optimal O(p/(B)+log_B n+nocc/B) I/Os, where B is the block size. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sahar Hooshmand and Paniz Abedin and M. Oguzhan Külekci and Sharma V. Thankachan 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.8 urn:nbn:de:0030-drops-87009 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.8 eng https://creativecommons.org/licenses/by/3.0/legalcode