A String Matching Algorithm Based on Efficient Hash Function

Based on the Karp-Rabin algorithm, a fast string matching algorithm is presented in this paper. It is also a hash-based approach, comparing the hash value of strings called fingerprint rather than the letters directly. The characteristic of the algorithm is that the hash function exploits bitwise operations and also considers about the size of the alphabet and the length of the pattern. We prove that the probability of a hash collision is minute and that the average running time is linear. Through a series of experiments, the remarkable performance of our algorithm is demonstrated.