Tag Archives: sub-string matching algorithms

Computer Algorithms: Rabin-Karp String Searching

Introduction

Brute force string matching is the a very basic sub-string matching algorithm, but it’s good for some reasons. For example it doesn’t require preprocessing of the text or the pattern. The problem is that it’s very slow. That is why in many cases brute force matching can’t be very useful. For pattern matching we need something faster, but to understand other sub-string matching algorithms let’s take a look once again on brute force matching.

In brute force sub-string matching we checked every single character from the text with the first character of the pattern. Once we have a match between them we shift the comparison between the second character of the pattern with the next character of the text, as shown on the picture below.

Brute Froce Principles
Brute force string matching is slow because it compares every single character from the pattern and the text!
Continue reading Computer Algorithms: Rabin-Karp String Searching