Faster string matching based on hashing and bit-parallelism

摘要

String matching is the process of finding the number of occurrences of a pattern P of length m in a text T of length n, where in practice m is much smaller than n. In this paper, we present a faster variation of HASHq based on improved hashing and greedy skip. Experimental results confirm that the proposed algorithm, namely FHASHq, is faster than HASHq, SBNDMq and FSBNDM algorithms on alphabets of size 4 (DNA alphabet), 128, 256, and 512. (C) 2017 Elsevier B.V. All rights reserved.