@inbook{5daeb7572c2749eeae381514a7345df2,
title = "Longest common prefixes with k-mismatches and applications",
abstract = "We propose a new algorithm for computing the longest prefix of each suffix of a given string of length n over a constant-sized alphabet of size σ that occurs elsewhere in the string with Hamming distance at most k. Specifically, we show that the proposed algorithm requires time O(n(σR) klog log n(log k+ log log n)) on average, where R= ⌈ (k+ 2) (log σn+ 1) ⌉, and space O(n). This improves upon the state-of-the-art average-case time complexity for the case when k= 1 [23] by a factor of log n/ log 3log n. In addition, we show how the proposed technique can be adapted and applied in order to compute the longest previous factors under the Hamming distance model within the same complexities. In terms of real-world applications, we show that our technique can be directly applied to the problem of genome mappability.",
author = "Hayam Alamro and Ayad, {Lorraine A.K.} and Panagiotis Charalampopoulos and Iliopoulos, {Costas S.} and Pissis, {Solon P.}",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-73117-9_45",
language = "English",
isbn = "9783319731162",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "636--649",
editor = "Jir{\'i} Wiedermann and Tjoa, {A Min} and Stefan Biffl and Ladjel Bellatreche and {van Leeuwen}, Jan",
booktitle = "SOFSEM 2018",
address = "Germany",
note = "44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018 ; Conference date: 29-01-2018 Through 02-02-2018",
}