A New String Matching Algorithm
Mustaq Ahmed, Mohammad Kaykobad, Rezaul Chowdhury · International Journal of Computer Mathematics · 2003
In this paper a new exact string-matching algorithm with sub-linear average case complexity has been presented. Unlike other sub-linear string-matching algorithms it never performs more than n text character comparisons while working on a text of length n . It requires only O ( m +σ) extra pre-processing time and space, where m is the length of the pattern and σ is the size of the alphabet.