String-matching algorithms

Target audience

This article is for people who’re already familiar with algorithm basics and have at least heard about string-matching algorithms but are still a bit scared of them.

Introduction

(it’s safe to skip to the next section)

When we think about string-matching algorithms, we tend to treat them the way we usually treat sorting algorithms. Like why the hell do I need to know how they work? As long it is O(N log N), why would I care?

There is one thing, though. Even though I’d argue this reasoning is correct if you think about direct applications of those, sometimes it is more than just that. If you need to sort an array, you’ll call a sort() method from the STL of your language, which will be enough. But think about a situation when you need to perform an on-disk sort, in which case you need to know why merge sort is the best for this purpose. Or, for example, if you need to find the p80 percentile (the typical use case for monitoring), then you better know how quicksort works.

Knowing those algorithms’ details is exciting and sometimes useful, and string-matching algorithms are no exception. This article will give you some pieces that helped me understand those algorithms better and made me less scared of them. Also, I’ll show you some applications of those to some leetcode problems, which are hard to identify as string matching when you first look at them. Although I’ll warn you straight away, that is not a…