32 _ 字符串匹配基础（上）：如何借助哈希算法实现高效字符串匹配？

从今天开始，我们来学习字符串匹配算法。字符串匹配这样一个功能，我想对于任何一个开发工程师来说，应该都不会陌生。我们用的最多的就是编程语言提供的字符串查找函数，比如Java中的indexOf()，Python中的find()函数等，它们底层就是依赖接下来要讲的字符串匹配算法。

字符串匹配算法很多，我会分四节来讲解。今天我会讲两种比较简单的、好理解的，它们分别是：BF算法和RK算法。下一节，我会讲两种比较难理解、但更加高效的，它们是：BM算法和KMP算法。

这两节讲的都是单模式串匹配的算法，也就是一个串跟一个串进行匹配。第三节、第四节，我会讲两种多模式串匹配算法，也就是在一个串中同时查找多个串，它们分别是Trie树和AC自动机。

今天讲的两个算法中，RK算法是BF算法的改进，它巧妙借助了我们前面讲过的哈希算法，让匹配的效率有了很大的提升。那RK算法是如何借助哈希算法来实现高效字符串匹配的呢？你可以带着这个问题，来学习今天的内容。

BF算法

BF算法中的BF是Brute Force的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。从名字可以看出，这种算法的字符串匹配方式很“暴力”，当然也就会比较简单、好懂，但相应的性能也不高。

在开始讲解这个算法之前，我先定义两个概念，方便我后面讲解。它们分别是主串和模式串。这俩概念很好理解，我举个例子你就懂了。

比方说，我们在字符串A中查找字符串B，那字符串A就是主串，字符串B就是模式串。我们把主串的长度记作n，模式串的长度记作m。因为我们是在主串中查找模式串，所以n>m。

作为最简单、最暴力的字符串匹配算法，BF算法的思想可以用一句话来概括，那就是，我们在主串中，检查起始位置分别是0、1、2....n-m且长度为m的n-m+1个子串，看有没有跟模式串匹配的。我举一个例子给你看看，你应该可以理解得更清楚。

从上面的算法思想和例子，我们可以看出，在极端情况下，比如主串是“aaaaa…aaaaaa”（省略号表