Info

新版网站会员 限时优惠；算法可视化编辑器上线，点击体验！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

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
// 8264

cpp 🤖

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

#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 🤖

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

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

go 🤖

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

import (
	"fmt"
	"strconv"
)

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

javascript 🤖

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

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

加载中...