滑动窗口延伸：Rabin Karp 字符匹配算法
原创约 8340 字
Note
网站新增大量习题，新增排序算法专题及可视化，具体请查看 网站更新日志~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 187. Repeated DNA Sequences | 187. 重复的DNA序列 | 🟠 |
| 28. Find the Index of the First Occurrence in a String | 28. 找出字符串中第一个匹配项的下标 | 🟠 |
经常有读者留言，请我讲讲那些比较经典的算法，我觉得有这个必要，主要有以下原因：
1、经典算法之所以经典，一定是因为有独特新颖的设计思想，那当然要带大家学习一波。
2、我会尽量从最简单、最基本的算法切入，带你亲手推导出来这些经典算法的设计思想，自然流畅地写出最终解法。一方面消除大多数人对算法的恐惧，另一方面可以避免很多人对算法死记硬背的错误习惯。
我之前用状态机的思路讲解了 KMP 算法，说实话 KMP 算法确实不太好理解。不过今天我来讲一讲字符串匹配的另一种经典算法：Rabin-Karp 算法，这是一个很简单优雅的算法。
本文会由浅入深地讲明白这个算法的核心思路，先从最简单的字符串转数字讲起，然后研究一道力扣题目，到最后你就会发现 Rabin-Karp 算法使用的就是滑动窗口技巧，直接套前文讲的 滑动窗口算法框架 就出来了，根本不用死记硬背。
废话不多说了，直接上干货。
首先，我问你一个很基础的问题，给你输入一个字符串形式的正整数，如何把它转化成数字的形式？很简单，下面这段代码就可以做到：
java 🟢
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
// 8264cpp 🤖
#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;
}python 🤖
s = "8264"
number = 0
for i in range(len(s)):
# 将字符转化成数字
number = 10 * number + (ord(s[i]) - ord('0'))
print(number)
# 打印输出：
# 8
# 82
# 826
# 8264go 🤖
s := "8264"
number := 0
for _, c := range s {
// 将字符转化成数字
number = 10*number + (int(c) - '0')
fmt.Println(number)
}
// 打印输出：
// 8
// 82
// 826
// 8264javascript 🤖
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