A Parallelized Naïve Algorithm for Pattern Matching

Abstract: The pattern matching is the problem of locating one string, a pattern, inside another, a text, which is required in for example databases, search engines, and text editors. Thus, several algorithms have been created to tackle this problem and this thesis evaluates whether a parallel version of the Naïve algorithm, given a reasonable amount of threads for a personal computer, could become more efficient than some state-of-the-art algorithms used today. Therefore, an algorithm from the Deadzone family, the Horspool algorithm, and a parallel Naïve algorithm was implemented and evaluated on two different sized alphabets. The results show that a parallel Naïve implementation is to be favoured over the Deadzone and Horspool on a alphabet of size 4 for patterns larger than 2 up to 20. Furthermore, for alphabet of size 256 the parallel Naïve should also be used for patterns of lengths 1 to 20.