Sliding Window Application: Rabin Karp String Matching Algorithm

Readers often leave messages asking me to discuss some classic algorithms, and I believe it's necessary to do so for the following reasons:

1. Classic algorithms are renowned for their unique and innovative design concepts, making it worthwhile to explore them together.

2. I aim to introduce these algorithms starting from the simplest and most fundamental concepts, guiding you to derive their design principles step by step, and naturally write the final solutions. This approach helps alleviate common fears about algorithms and prevents the habit of rote memorization.

Today, we'll delve into the classic Rabin-Karp string matching algorithm.

This article will thoroughly explain the core ideas of this algorithm, starting with the simplest concept of converting strings to numbers. We will then explore a LeetCode problem, leading to the realization that the Rabin-Karp algorithm employs the sliding window technique. You can directly apply the Sliding Window Algorithm Framework discussed earlier, without the need for rote memorization.

Without further ado, let's dive into the content.

First, a basic question for you: given a string representation of a positive integer, how do you convert it into a numeric form? It's quite simple; the following code 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