String pattern matching algorithms

OData support
Supervisor:
Dr. Dudás Ákos
Department of Automation and Applied Informatics

The problem of exact string matching is that there are two strings, one main text, and one other – called pattern –, and we have to find all appearances of the pattern in the main text. Although this task may sound trivial at first, it can be challenging to achieve good matching times, and reasonable memory usage – especially when matching on a long text. Several distinct approaches exist to solve this problem, from which we will choose two rather different ones for examination.

Following the present technological advancement we will inspect the possibilities to parallelize both of the algorithms. We will then show parallel implementations for both.

We will present both string matching algorithms’ single threaded and parallel implementations, all written in four different programming languages. We will then compare these implementations’ running time, memory usage and speedup gained from parallelization.

In the end, we will demonstrate a string matching framework created from the formerly presented implementations. The main purpose of this framework is to make these implementations reusable by other projects – even by programmers who are not aware of the details of the algorithms.

Downloads

Please sign in to download the files of this thesis.