滑动窗口延伸：Rabin Karp 字符匹配算法

经常有读者留言，请我讲讲那些比较经典的算法，我觉得有这个必要，主要有以下原因：

1、经典算法之所以经典，一定是因为有独特新颖的设计思想，那当然要带大家学习一波。

2、我会尽量从最简单、最基本的算法切入，带你亲手推导出来这些经典算法的设计思想，自然流畅地写出最终解法。一方面消除大多数人对算法的恐惧，另一方面可以避免很多人对算法死记硬背的错误习惯。

我之前用状态机的思路讲解了 KMP 算法，说实话 KMP 算法确实不太好理解。不过今天我来讲一讲字符串匹配的另一种经典算法：Rabin-Karp 算法，这是一个很简单优雅的算法。

本文会由浅入深地讲明白这个算法的核心思路，先从最简单的字符串转数字讲起，然后研究一道力扣题目，到最后你就会发现 Rabin-Karp 算法使用的就是滑动窗口技巧，直接套前文讲的 滑动窗口算法框架 就出来了，根本不用死记硬背。

废话不多说了，直接上干货。

首先，我问你一个很基础的问题，给你输入一个字符串形式的正整数，如何把它转化成数字的形式？很简单，下面这段代码就可以做到：

String s = "8264";
int number = 0;
for (int i = 0; i < s.length(); i++) {
    // 将字符转化成数字
    number = 10 * number + (s.charAt(i) - '0');
    System.out.println(number);
}
// 打印输出：
// 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++) {
        // 将字符转化成数字
        number = 10 * number + (s[i] - '0');
        cout << number << endl;
    }
    // 打印输出：
    // 8
    // 82
    // 826
    // 8264
    return 0;
}

s = "8264"
number = 0
for i in range(len(s)):
    # 将字符转化成数字
    number = 10 * number + (ord(s[i]) - ord('0'))
    print(number)
# 打印输出：
# 8
# 82
# 826
# 8264

s := "8264"
number := 0
for _, c := range s {
    // 将字符转化成数字
    number = 10*number + (int(c) - '0')
    fmt.Println(number)
}
// 打印输出：
// 8
// 82
// 826
// 8264

var s = "8264";
var number = 0;
for (var i = 0; i < s.length; i++) {
    // 将字符转化成数字
    number = 10 * number + (s.charAt(i) - '0');
    console.log(number);
}
// 打印输出：
// 8
// 82
// 826
// 8264