The k-mismatch problem revisited

Autor: Ely Porat, Benjamin Sach, Tatiana Starikovskaia, Allyx Fontaine, Raphaël Clifford

Publikováno v: Clifford, R, Fontaine, A, Porat, E, Sach, B & Starikovskaia, T 2016, The k-mismatch problem revisited . in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms . vol. January 2016, Society for Industrial and Applied Mathematics, pp. 2039-2052 . https://doi.org/10.1137/1.9781611974331.ch142

We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and every m-length substring of a text of length n, as long as that Hamming

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fe81c5274c83dd0b3e81f2855d1ba5f7