Sliding Window Application: Rabin Karp String Matching Algorithm

Many readers ask me to explain some classic algorithms. I think this is important for a few reasons:

1. Classic algorithms are classic because they have unique and interesting ideas. So we should learn them together.

2. I will start from the simplest and most basic ideas, and guide you to understand how these classic algorithms are designed. This can help you write the solutions naturally, remove your fear of algorithms, and avoid the bad habit of memorizing algorithms without understanding.

Today, let's talk about the classic Rabin-Karp string matching algorithm.

In this article, I will explain the main idea of this algorithm in a simple way. First, we start from converting a string to a number. Then, we will look at a LeetCode problem. In the end, you will see that the Rabin-Karp algorithm is actually using the sliding window technique, just like the Sliding Window Algorithm Framework we discussed before. There is no need to memorize it.

Let's get started.

First, let me ask you a basic question: If you are given a string that represents a positive integer, how do you convert it to a number? It's very simple. The code below does this:

String s = "8264";
int number = 0;
for (int i = 0; i < s.length(); i++) {
    // convert the character to a number
    number = 10 * number + (s.charAt(i) - '0');
    System.out.println(number);
}
// print output:
// 8
// 82
// 826
// 8264

#include<iostream>
#include<string>
using namespace std;

int main() {
    string s = "8264";
    int number = 0;
    for (int i = 0; i < s.size(); i++) {
        // convert character to number
        number = 10 * number + (s[i] - '0');
        cout << number << endl;
    }
    // print output:
    // 8
    // 82
    // 826
    // 8264
    return 0;
}

s = "8264"
number = 0
for i in range(len(s)):
    # convert character to number
    number = 10 * number + (ord(s[i]) - ord('0'))
    print(number)
# print output:
# 8
# 82
# 826
# 8264

s := "8264"
number := 0
for _, c := range s {
    // convert the character to a number
    number = 10*number + (int(c) - '0')
    fmt.Println(number)
}
// print output:
// 8
// 82
// 826
// 8264

var s = "8264";
var number = 0;
for (var i = 0; i < s.length; i++) {
    // convert the character to a number
    number = 10 * number + (s.charAt(i) - '0');
    console.log(number);
}
// print output:
// 8
// 82
// 826
// 8264

Efficiently Find Repeated Subsequences

Rabin-Karp Algorithm