数据结构与算法分析（十六）--- 如何设计更高效的字符串匹配算法？(BF + RK + KMP + BMH)

字符处理操作作为计算机的核心任务之一，各种编程语言都为其提供了丰富的字符处理函数库，比如前两篇博文介绍的C语言字符处理和C++ string 与regex class 操作。字符处理操作中最常用的应该算是字符串查找匹配操作了，比如C 语言提供的strstr()函数和C++ 提供的find()函数、search()函数、regex_match()函数、regex_search()函数等，这些字符串查找匹配函数都使用什么字符串匹配算法呢？这些字符串匹配算法是如何对基础的匹配算法进行优化的？是否能像排序算法那样，欣赏到类似归并、快速等高级排序算法对插入、选择等基础排序算法的巧妙优化，让我们大开眼界呢？

一、Brute Force 匹配算法

Brute Force 算法中文翻译过来叫暴力匹配算法或者朴素匹配算法，从字面意思看就是没使用什么特别的优化技巧，逐字符比对，像下面图示这样：

BF 匹配算法从主字符串txt 和模式串pat 的首字符开始对比，根据匹配结果可分两种情况分析：

1. 如果主串和模式串字符匹配，指向两个字符的游标 i 和 j 都后移一位对比下一个字符（也即 i++, j++）；
2. 如果主串与模式串字符不匹配，指向两个字符的游标 i 和 j 都回到模式串首字符位置（也即 i = i - j, j =0），主串当前字符已验证不匹配，因此再后移一个字符继续比较（也即 i = i - j + 1）；

将上面的思路翻译为实现代码如下：

char* BF_match(const char* str, const char* pat)
{
   
    if(str == NULL || pat == NULL)
		return NULL;
 
	size_t i = 0, j = 0;
	while (str[i] != '\0' && pat[j] != '\0') {
   
		if (str[i] == pat[j]) {
   
			// 如果当前字符匹配成功，则主串与模式串游标都后移一位，对比下一个字符
			i++;
			j++;
		} else {
   
			// 如果当前字符不匹配，则将模式串游标移到首字符处，主串游标移到与模式串首字符对应的下一个位置
			i = i - j + 1;
			j = 0;
		}
	}
	// 匹配成功，返回模式串pat 在主串str 中的位置，否则返回 -1
	if (pat[j] == '\0')
		return (char *)(str + i - j);
	else
		return NULL;
}

从上面的算法思想可以看出，在极端情况下（比如长度为n 的主串”aaa…aaa“，长度为m 的模式串”aa…b“），每次都比对m 个字符，要比对n - m + 1 次，BF 算法的最坏情况时间复杂度为 O(n * m)。

从BF 算法的时间复杂度可知，如果模式串的长度m 比较小，BF 算法的效率还是不错的。在实际开发中，大部分情况下模式串确实都比较短，而且该算法代码实现比较简单，空间复杂度为O(1)，所以还是挺常用的。比如早期C 标准库提供的strstr() 函数就采用了BF 匹配算法，实现代码如下（基于GCC-4.8.0 实现，为区别C标准库函数修改了函数名）：

#include <string.h>

char* STR_match(const char *str, const char *pat)
{
   
    if(str == NULL || pat == NULL)
		return NULL;

    const size_t pLen = strlen(pat);
    const char *pos = str;
    // 先找到主串与模式串首字符匹配的位置，找不到则返回空指针
    while ((pos = strchr(pos, pat[0])) != NULL) {
   
        // 主串与模式串首字符匹配，则继续比较后面的pLen - 1 个字符
        if(strncmp(pos, pat, pLen) == 0)
            return (char *) pos;    // 如果匹配成功，则返回主串匹配首字符指针
        ++pos;  // 若匹配失败，则主串游标后移一位，继续查找与模式串首字符匹配的位置
    }
    return NULL;
}

二、Rabin–Karp 匹配算法

如果模式串比较长，我们不满足于O(n * m) 的时间复杂度，该如何优化呢？算法优化有一个核心原则：从信息论角度分析，尽可能高效的挖掘使用更多信息，让计算机少做事情，是算法优化的切入点。

从这个角度思考分析，BF 算法有两个优化方向：

1. BF 算法逐个字符比较效率较低，能否省去逐字符比较过程，直接对比模式串和主串中等长的字符序列呢？
2. BF 算法遇到匹配失败的字符总是往前回到初始位置开始比较，主串游标每次只后移一位，能否充分利用已经对比过的字符信息跳过一些不可能匹配的情况，让主串游标每次可以后移多位呢？

先分析第一种优化方向，能否在O(1) 时间复杂度内比较两个长度为m 的字符串呢？一般情况下，两个定长数值可以在常数时间获得比较结果，能否将变长字符串转换为定长数值呢？我们很容易想到哈希散列函数（可参阅博文：哈希算法能用来干啥？），比如著名的消息摘要算法MD5 可以将一个文件转换为一个128 位的散列值，自然也可以将一个字符串转换为定长的hash value，然后在常数时间内比较是否相等，达到省去逐字符比较的优化目的。

当然MD5 哈希运算比较耗时，如果比较的主串和模式串字符种类比较少，可以设计更简单的哈希算法，比如只包含26 个字母可以将字符串转换为26 进制数值，甚至可以直接将各字符的编码值相加获得该字符串的哈希值。

著名的Rabin-Karp 字符串匹配算法就是采用这种思路对BF 算法进行优化的，而且充分利用主串中两个相邻子串哈希值计算的关系（也即使用滚动哈希算法），进一步提高哈希计算效率，将主串中所有与模式串等长子串的哈希值计算时间复杂度提高到O(n)。模式串与每个子串哈希值比较的时间复杂度为O(1)，最多需要比较 (n - m + 1) 个子串，因此RK 字符串匹配算法的时间复杂度为O(2n - m + 1)，简写为O(n)。

使用两个字符串的哈希值比对，还需要注意哈希冲突的问题，如果存在大量的哈希冲突，RK 匹配算法的时间复杂度也会退化。如果两个字符串的哈希值不一致则两个字符串肯定不匹配，如果两个字符串的哈希值一致，不能保证两个字符串能够匹配，为了防止是哈希冲突的情况，还需要再次逐个字符比对两个字符串，才能确保两个字符串是否匹配。

本文主要介绍RK 算法的实现思路，哈希算法就采用最简单的形式，将字符串中各字符的ASCII 值相加便得到其哈希值，为防止字符串过长而超出类型极限，对其进行取余计算。计算出第一个哈希值hash[0] 后，使用滚动哈希算法计算后续的哈希值：

hash[i + 1] = hash[i] - str[i] + str[i + strlen(pat)];

计算完模式串及主串中各子串的哈希值并保存到hash 数组中，后续只需要逐个比对哈希值即可，若哈希值相等再使用C 标准库中的strncmp 函数比较模式串与哈希值匹配的子串，若二者匹配则直接返回，RK 算法的实现代码如下：

#include<stdlib.h>
#include<string.h>
#include<stdint.h>
#include<limits.h>

size_t* Roll_hash(const char* str, const char* pat, const size_t pLen, const size_t sNum)
{
   
    // 为各子串及其模式串哈希值分配存储空间，hash[sNum]存储模式串哈希值，故分配sNum + 1 个元素
    size_t* hash = malloc((sNum + 1) * sizeof(size_t));
    if(hash == NULL) return NULL;
    size_t sHash = 0, pHash = 0;
    // 哈希函数使用最简单的将各字符ASCII 值相加
    for (size_t i = 0; i < pLen; i++) {
   
        sHash += (size_t)str[i];
        pHash += (size_t)pat[i];
    }
    hash[0] = sHash % (SIZE_MAX - CHAR_MAX);         // 存储主串中第一个与模式串等长的子串哈希值，并取余以防超出类型极限
    hash[sNum] = pHash % (SIZE_MAX - CHAR_MAX);      // 存储模式串哈希值，对(SIZE_MAX - CHAR_MAX)取余，后面滚动计算哈希值时可保证不超限
    // 采用滚动哈希算法，主串中各子串哈希值都根据前一个哈希值计算得出，因hash[0] < (SIZE_MAX - CHAR_MAX)，后续哈希值不用取余也可保证不超限
    for (size_t j = 1; j < sNum; j++)
        hash[j] = hash[j - 1] - (size_t)str[j - 1] + (size_t)str[j - 1 + pLen];
    
    return hash;
}

char* RK_match(const char* str, const char* pat)
{
   
    if(str == NULL || pat == NULL)
		return NULL;
    // 计算模式串长度，以及主串中与模式串等长的子串数量
    size_t pLen = strlen(pat);
    size_t sLen = strlen