String searching with mismatches using AVX2 and AVX-512 instructions

We present new algorithms for the k mismatches version of approximate string matching. Our algorithms utilize the SIMD (Single Instruction Multiple Data) instruction set extensions, particularly AVX2 and AVX-512 instructions. Our approach is an extension of an earlier algorithm for exact string matching with SSE2 and AVX2. In addition, we modify this exact string matching algorithm to work with AVX-512. We demonstrate the competitiveness of our solutions by practical experiments. Our algorithms outperform earlier algorithms for both exact and approximate string matching on various benchmark data sets. • New algorithms for the k mismatches version of approximate string matching. • We modify the exact string-matching algorithm to work with AVX-512. • Demonstrate the competitiveness of our solutions by practical experiments.