Sliding Window Application: Rabin Karp String Matching Algorithm

Many readers often leave comments asking me to explain some classic algorithms. I think it's necessary for the following reasons:

1. Classic algorithms are considered classic because they have unique and innovative design ideas, so it's essential to guide everyone through learning them.

2. I will try to start with the simplest and most basic algorithms, leading you to derive the design ideas of these classic algorithms step by step, and naturally write the final solutions. This approach aims to eliminate the fear of algorithms for most people and avoid the common mistake of rote memorization.

Previously, I explained the KMP algorithm using the state machine approach. Honestly, the KMP algorithm can be a bit challenging to understand. However, today I will introduce another classic string matching algorithm: the Rabin-Karp algorithm, which is simple and elegant.

This article will explain the core idea of this algorithm from the basics, starting with converting strings to numbers, then exploring a LeetCode problem. By the end, you will realize that the Rabin-Karp algorithm utilizes the sliding window technique, which directly fits the Sliding Window Algorithm Framework discussed earlier, so there's no need to memorize it by rote.

Enough chatter, let's dive into the content.

First, let me ask you a very basic question: Given a string representation of a positive integer, how do you convert it into a numerical form? It's simple; the following code snippet can achieve 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