字符串匹配的算法有很多，本篇文章主要介绍两种比较简单的算法：BF算法和RK算法。

准备

在开始讲解算法之前，我们先了解两个概念：主串和模式串。这俩概念很好理解，我举个例子你就懂了：

我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。

BF算法

BF 算法的全称为 Brute Force 算法，中文叫做暴力匹配算法，也叫朴素匹配算法。顾名思义，这个算法简单暴力。但同样的，算法效率也不是很高。

算法思想

既然是简单暴力的算法，BF算法的思想也可以用一句话概括：在主串中，依次遍历起始位置为0，1，2，……，n - m 且长度为 m 的 n - m + 1 个子串，看是否有和模式串相同的子串。(其中 n 为主串的长度，m 为模式串的长度)

代码实现

这里放一份我顺手写的代码吧(仅供参考)：

/**
 * \brief BF算法
 * \param main_string 主串
 * \param pattern_string 模式串
 * \return 主串中是否存在模式串
 */
int BF_find(const string& main_string, const string& pattern_string)
{
    const int len = main_string.length() - pattern_string.length();

    for (auto i = 0; i <= len; i++)
    {
        // 找到和模式串第一个字符相同的
        if (main_string[i] == pattern_string[0])
        {
            bool same = true;

            // 判断剩下的是否相同
            for (auto j = 0; j < pattern_string.length(); j++)
            {
                if (main_string[i + j] != pattern_string[j])
                {
                    same = false;
                    break;
                }
            }

            // 相同则返回偏移量
            if (same)
                return i;
        }
    }

    return -1;
}

可以很容易看出：在极端情况下，比如在 aaa……aaaa 这样一个字符串中匹配 aaab 这样的字符串，我们就需要匹配 n - m + 1 次，每次匹配 m 个字符。所以该算法的最坏时间复杂度就是 O(m*n)。

RK算法

RK算法全称叫做 Rabin-Karp算法。是由 Rabin 和 Karp 共同提出的一个算法。
RK算法是对BF算法的一个改进：在BF算法中，每一个字符都需要进行比较，并且当我们发现首字符匹配时仍然需要比较剩余的所有字符。而在RK算法中，就尝试只进行一次比较来判定两者是否相等。

那么它是如何做到一次比较就判断相等呢？让我们来看看它是怎么做的：

算法思想

BF算法在检查子串和模板串是否相同的时候是逐字符比对的，这就导致了它的时间复杂度比较高。但如果我们稍微改造一下对比的方法，引入哈希算法，复杂度就会降低许多。

所以RK算法的思路如下：将模式串的 hash 值跟主串中的每一个长度为 m 的子串的 hash 值比较。如果不同，则它们肯定不相等；如果相同，由于哈希冲突存在，再逐字符的比较。
因为哈希后是一个数字，数字之间的比较是非常快的，所以模式串和子串的比较就快了很多。

不过虽然模式串和子串的比较变快了，但是计算哈希需要遍历子串，所以整体时间复杂度似乎还是不变。这个如何解决呢？

这就需要哈希函数设计的有技巧了。我们可以假设我们要匹配的字符串只包含 K 个字符，那么我们就可以将其转化为一个 K 进制数，然后转化为十进制作为子串的哈希值。

举个小例子：假设我们要处理的的字符串只包含 a-z 这 26 个小写字母，那我们就用26进制来表示这个字符串。a 表示 0，b 表示 1，以此类推。

比如字符串 "cba" 进行运算的过程为：
"cba" = 'c' 26 26 + 'b' * 26 + 'a'

  = 2 * 26 * 26 + 1 * 26 + 0
  = 1353

时间复杂度

上面说 RK 算法比 BF 算法更快，那我们就来分析一下 RK算法的时间复杂度吧：

• 计算哈希值可以通过一些方法，比如查表，快速的算出哈希值，复杂度约为 O(n)
• 模式串和子串哈希值比较的时间复杂度为 O(1)
• 总共需比较 n - m + 1 次

所以整体的时间复杂度大约为 O(n)。

数据溢出

我们刚才使用的 K 进制的方法是没有散列冲突的。但是有一个问题，如果字符串过长，很可能超过计算机中整型数据的最大值的。这里哦我们可以通过允许一些散列冲突，让转换后的数可以存在整型数据中。

比如不将字符串当成一个 K 进制数，而是将每个字符转换为整型数后再相加。当然方法不止这一种，这个方法只是举例。

散列冲突

那么新的问题来了，上面说了我们会有一些散列冲突的情况发生，所以我们需要判定是不是散列冲突的情况。

这种其实很好判断。只需要再将子串和模式串逐字节比较一下就好了。因为哈希值不一样的一定不相等，所以还是可以提高一些效率的。

代码实现

随便写的参考代码，有问题请大佬指正：

/**
 * \brief RK算法
 * \param main_string 主串
 * \param pattern_string 模式串
 * \return 模式串在主串中的偏移量
 */
int RK_find(const string& main_string, const string& pattern_string)
{
    const int len = main_string.length() - pattern_string.length();
    int refer = 0; // 模式串的哈希值

    // 使用字符的 ASCII 码之和当作哈希
    for (auto& i : pattern_string)
        refer += static_cast<int>(i);

    for (auto i = 0; i <= len; i++)
    {
        int cmp = 0; // 子串的 hash 值

        for (auto j = 0; j < pattern_string.length(); j++)
            cmp += static_cast<int>(main_string[i + j]);

        // 如果哈希值相同，则判断是否为散列冲突
        if (cmp == refer)
        {
            bool same = true;
            
            for (auto j = 0; j < pattern_string.length(); j++)
            {
                if (main_string[i + j] != pattern_string[j])
                {
                    same = false;
                    break;
                }
            }

            // 相同则返回偏移值
            if (same)
                return i;
        }
    }

    return -1;
}