Counting mismatches with SIMD

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


Research units


We consider the k mismatches version of approximate string matching for a single pattern and multiple patterns. For these problems we present new algorithms utilizing the SIMD (Single Instruction Multiple Data) instruction set extensions for patterns of up to 32 characters. We apply SIMD computation in two ways: in counting of mismatches and in calculation of fingerprints. We demonstrate the competitiveness of our solutions by practical experiments.


Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2017
EditorsJan Holub, Jan Zdarek
Publication statusPublished - 2017
MoE publication typeA4 Article in a conference publication
EventPrague Stringology Conference - Prague, Czech Republic
Duration: 28 Aug 201730 Aug 2017
Conference number: 21


ConferencePrague Stringology Conference
Abbreviated titlePSC
CountryCzech Republic

    Research areas

  • Approximate string matching, SIMD instructions, algorithm engineering

ID: 16434781