String Algorithms

A quick summary of 5 string algorithms: Naive, Knuth–Morris–Pratt, Boyer Moore Algorithm, String Hash, Suffix Trie.

TL;DR;

The algorithms cheat sheet is given at the end of the article.

What’s the first thing that comes to your mind when you hear the word algorithms? Binary Search, Divide-and-conquer, DFS algorithms, I suppose. And what about the String Algorithms?

Let’s talk about the most famous String algorithms in this article.

What are the String algorithms?

Algorithms, which are used for searching a string within another string.

Use cases vary from Natural Language Processing to Plagiarism Detection, Search Engines, and Database Schemas. For instance, have you ever mistyped a word and searched for it? And have you seen Google’s `Did you mean …` message? That’s it. Another beautiful example is a search for text within the website, pdf file, or document.

The purpose of the string matching algorithms is to find an exact one or several occurrences of a given string (pattern/needle) in a larger string (sequence/haystack) or a text.

In this article, I’ll provide a cheat sheet for some string-searching algorithms, aka string-matching algorithms, after a quick introduction to each of them.

There’s few algorithms mentioned here:

1. Naïve Algorithm

A brute force approach, which checks all characters of the sequence.

✏️ Consider searching for abcin aaaaaabc.
⚙️ It slides the haystack one by one to see the occurrence. If there’s one found, it slides again to the following occurrences.

🏆 What are its best and worst cases?

• The best case is when the needle is not present in the haystack, so it does not need to slide again.
• The worst case can be seen when only the last element of the haystack is different or when all elements of the haystack include the needle (xxin xxxxxxxxxx).

So, searching for a string with a brute approach will result in the time complexity of O(n*m) and in O(m*(n-m+1)) in the worst case, where m is the length of the pattern/needle and the n is the length of the sequence/haystack.

2. Knuth–Morris–Pratt algorithm (KMP)

This is an improved version of the Naive Algorithm for the haystack with a needle appearing more than once in it.

⚙️ The algorithm does not traverse the haystack one by one, instead, when a mismatch is found, the KMP starts to seek a match from the character where the match was found.

✏️ Consider an example:

haystack = 'ABCACD', needle = 'ABCAB';

The iteration will be as follows:

Table 1: Comparison of Naive and KMP algorithms

So, in KMP, the haystack is traversed once the time complexity is O(n) even for the worst case.

3. Boyer Moore Algorithm:

This is a Naive and KMP algorithms combo.

⚙️ It preprocesses the string as KMP and uses it to skip the mismatches. One important point is that it starts matching from the last character of the needle.

The algorithm uses two rules:

• the bad character rule and
• the good suffix rule

The maximum offset retrieved from these two rules is the actual offset, that will be applied.

The bad character rule

1. The needle is searched from the last character and the comparison starts to the left.

2. Once there’s a mismatch found, that is marked as a bad character.

3. Next, the bad character is searched to the left of the needle

4. If such a character is found, that is brought to the bad character’s offset.

Get Aziza Kasenova’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

✏️ Consider an example:

haystack = 'HELLOXWORLDXHEYWORLD', needle = 'XHEYWORLD';

The iteration will be as follows:

Table 2: Bad rule iteration

The good suffix rule

Developed because the bad character rule might not always give the best suggestion.

1. The needle is searched from the last characters forming a sub-pattern p from the needle and the comparison starts to the left.

2. Once there’s a mismatch found, then check the next occurrence, p’, of the p from the left. There are a few more rules to be taken into the account, which I will explain with the example below.

✏️ Consider an example:

haystack = ‘xyziHEYyABCxABCxABC’, needle = ‘yABCxABC’;

The iteration will be as follows:

Table 3: Good suffix iteration

In case the p’ is not found, they find the smallest shift possible that matches the prefix of the needle to the suffix p in the haystack.

In case there is no such shift possible, shift the needle by its length, so that the needle passes p.

4. String Hash

An idea here is to convert the string into a number, the hash of the string, by using a hash function.

Two strings are said to be equal if their hashes are equal, so if H(x) === H (y), then x = y.

⚙️A polynomial mod some prime p is the most powerful and easiest hash function, with the below formula:

H(x1 . . . xk) = x[1]a^(k−1) + x[2]a^(k−2) + · · · + x[k−1]a + x[k] * (mod p)

5. Suffix Trie

Trie is a tree data structure to store the strings, one character in every node.

Below is the visualization of trie containing the words HELLO, HEY, HUMAN and HUMBLE.

A trie example

A suffix trie stores each unique suffix in every node.

This can be visualized as follows:

Suffix trie example

where um from human and humble form a unique suffix.

Once the trie is built, searching for a string in it will take O(n) amount of time, where n is the length of the text.

Summarizing all, there can be a below cheat sheet retrieved for

• Naive
• Knuth–Morris–Pratt algorithm (KMP)
• Boyer Moore
• String Hash and
• Suffix Trie

algorithms:

where n and m stand for the length of the haystack and a needle.

Hope, you enjoyed reading it! 🤞

Let me know, if you need a summary for other string algorithms.

Open for your comments and suggestions in the comments 📝.
And feel free to contact me on LinkedIn as well.