2026-07-26T19:28:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13956 2024-03-06T10:52:59Z ddc:004 open_access

The k-Mappability Problem Revisited Amir, Amihood Boneh, Itai Kondratovsky, Eitan Pattern Matching Hamming Distance Suffix Tree Suffix Array The k-mappability problem has two integers parameters m and k. For every subword of size m in a text S, we wish to report the number of indices in S in which the word occurs with at most k mismatches. The problem was lately tackled by Alzamel et al. [Mai Alzamel et al., 2018]. For a text with constant alphabet Σ and k ∈ O(1), they present an algorithm with linear space and O(nlog^{k+1}n) time. For the case in which k = 1 and a constant size alphabet, a faster algorithm with linear space and O(nlog(n)log log(n)) time was presented in [Mai Alzamel et al., 2020]. In this work, we enhance the techniques of [Mai Alzamel et al., 2020] to obtain an algorithm with linear space and O(n log(n)) time for k = 1. Our algorithm removes the constraint of the alphabet being of constant size. We also present linear algorithms for the case of k = 1, |Σ| ∈ O(1) and m = Ω(√n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amihood Amir and Itai Boneh and Eitan Kondratovsky 2021 Is Part Of LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2021.5 urn:nbn:de:0030-drops-139566 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.5 eng https://creativecommons.org/licenses/by/4.0/legalcode