Evaluating Performance of Pattern Searching Algorithms on Wildcard Patterns

Sammanfattning: The pattern matching problem is the problem of finding a set of sequential characters in a text of equal amount of characters or more. There are many applications for pattern matching algorithms e.g. search engines and databases. Some algorithms allow for multiple patterns to be searched for at the same time. One such algorithm is the Aho-Corasick (AC) algorithm, it is an extension of the single-pattern matching algorithm called Knuth-Morris-Pratt (KMP). The aim of this thesis is to find out if multiple executions of KMP can match multi-patterns faster than AC in regards to wall-clock time. The results show that the time it takes for KMP to execute is barely affected by pattern length, while AC gets slower when the pattern length increases. KMP is faster than AC when the pattern length is long in relation to the texts length, and parallel executions of KMP is faster than sequential when there are more than 2 patterns.