算法字符串

字符串精确匹配的主流算法总结（含书籍推荐）

字数统计: 2k字   |   阅读时长: 7分
, , , ,

摘要: 字符串精确匹配方法汇总

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，此前我们讨论了字符串精确匹配的很多主流算法。

实际上字符串匹配算法是一个单独的大课题，这里推荐一本书 《Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology》 作者 Dan Gusfield。

在书中，“精确字符串匹配”被视为一个基础问题，作者从暴力方法开始讲解，逐步引入预处理方法，包括对模式和文本的预处理。作者探讨了基于比较的经典方法，如 Boyer-Moore 算法、Knuth-Morris-Pratt 算法。

另一方面，书中介绍了后缀树的概念及其应用，后缀树是一种强大的数据结构，可以用于解决字符串相关的许多问题。作者从后缀树的基本定义开始，给出了一些历史背景和简单的例子。

在更深入地介绍经典算法之后，书中还探讨了半数值字符串匹配方法以及与基于比较的方法的差异。如 Shift-And 方法和匹配计数问题，以及使用快速傅里叶变换（FFT）来解决问题的技术。此外 Karp-Rabin 指纹算法也就是字符串哈希也是讨论重点之一。这些方法有助于提高字符串匹配算法在不同场景下的效率和准确性。

总体而言，这本书提供了一个全面的视角，来理解和运用与字符串、树和序列相关的算法。可以通过以下链接下载。

本文我们以 leetcode 第 28 题为模板题，总结一下字符串精确匹配的各种主流算法。

28. 实现 strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：
输入：haystack = “sadbutsad”, needle = “sad”
输出：0
解释：”sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：
输入：haystack = “leetcode”, needle = “leeto”
输出：-1
解释：”leeto” 没有在 “leetcode” 中出现，所以返回 -1 。

提示：

1
2
1 <= haystack.length, needle.length <= 1e4
haystack 和 needle 仅由小写英文字符组成

算法1: 暴力(双指针)

字符串精确匹配是指在目标文本串 s(s[0..n-1])，中检索子串 p(p[0..m-1]) 的过程。

s 称为主串，长度为 n，p 称为模式串，长度为 m。

暴力算法也称 BF(Brute Force) 算法，核心思想是枚举主串的各个字符，作为子串的起点，然后比较各个子串与模式串是否相等。s 一共有 n - m + 1 个子串， 需要枚举 n - m + 1 个起点(0, 1, …, n - m)。

对于每个枚举到的子串，与模式串 p 进行逐字符比较，子串的比较时间复杂度 $O(m)$，总时间复杂度 $O(m(n-m))$。

BF 算法的低效主要是由于某个子串匹配失败时，s[i] != p[j]，需要将 i, j 都回溯。没有利用 p[0..j-1] 部分匹配的结果。

参考文章 暴力算法更实用：字符串匹配平均比较次数。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()) return 0;
        if(haystack.empty()) return -1;
        int n = haystack.size(), m = needle.size();
        if(n < m) return -1;
        int left = 0;
        while(left <= n - m)
        {
            if(haystack[left] == needle[0])
            {
                int right = left + 1;
                while(right - left < m)
                {
                    if(haystack[right] == needle[right - left]) ++right;
                    else break;
                }
                if(right - left == m) return left;
            }
            ++left;
        }
        return -1;
    }
};

算法2: 字符串哈希

字符串哈希的思想是，要对比两个字符串，首先对比两个字符串对应的哈希值，如果连哈希值都不一样，那这两个字符串肯定不相等，如果哈希值一样，则这两个字符串大概率相等，但还是存在不相等的可能，需要额外验证。

于是在 s 中检索子串 p 的过程就是枚举 s 的所有长为 m 的子串，然后对比子串与 p 对应的哈希值：

  • 若哈希值不相等，则该子串与 p 不相等；
  • 若哈希值相等，则对比子串与 p 的每个字符，确认子串确实等于 p。

这种做法想要高效，需要在对比完子串 s[i..i+m-1] 与模式串 p 之后，在对比子串 s[i+1..i+m] 与模式串 p 的时候，算子串 s[i..i+m-1] 的哈希值只需要 $O(1)$ 地处理新字符 s[i+m] 即可，而 s[i+1..i+m-1] 这部分可以基于此前计算的结果。常见的有两种处理方式：滚动的处理方式与前缀的处理方式。

通过字符串哈希解决字符串精确匹配问题的原理与实现，参考文章 字符串哈希。

算法3: MP 与 KMP

MP 算法是 Morris, Pratt 在 1970 提出的算法。与暴力算法相比的改进主要体现在：某次匹配失败时候，i 不回溯，j 往前回溯若干位。而 j 往前回溯多少位，由一个失效函数控制。

KMP 指的是 Kruth-Morris-Pratt 这三个人，是 1977 年提出的算法。与 MP 算法的区别仅在于一处。一般也把 MP 和 KMP 算法分别称为 KMP 和扩展 KMP 算法。

MP 和 KMP 算法的具体细节参考文章 KMP算法与代码模板。

KMP 算法比较难，但是其思想比较重要，很多字符串上的算法的优化都基于了 KMP 的仅回溯若干位这个线索。

算法4: BM 算法

BM 算法是算法，Boyer 和 Moore 在 1977 年提出的算法。它通过预处理文本字符串，创建一个坏字符表（bad character table）和一个好后缀表（good suffix table），在搜索过程中利用这些表来跳过不可能包含模式串的子串，从而提高搜索效率。与 KMP 类似，这是一种先预处理再响应查询的思路。

BM 算法有两个常见的变种，一个是 Horspool 算法，这是 BM 的一个简化版本，由 Nigel Horspool 在 1980 年提出，另一个是 Sunday 算法，在 BM 的基础上做了一些改动。1990 年 Daniel M.Sunday 提出。

BM 算法、Horspool 算法和 Sunday 算法的细节与代码，参考下列文章：

STL 中与匹配相关的算法

以下 STL 中的组件涉及到字符串精确匹配。

  • std::find, std::find_if, std::find_if_not
  • std::search, std::search_n
  • std::regex_match, std::regex_search, std::regex_replace

此外在 gcc 中 strstr 的朴素实现可以参考以下代码：

https://github.com/gcc-mirror/gcc/blob/41d6b10e96a1de98e90a7c0378437c3255814b16/libiberty/strstr.c

里面有句注释，如果系统有自带 strstr 的话，优先用系统的 strstr 而不是 gcc 的。

1
2
/* Simple implementation of strstr for systems without it.
   This function is in the public domain.  */

std::string::find 函数和 C 的标准库中 strstr 函数实现类似，std::string::find 用的就是暴力算法。在大多数常见场景下，需要匹配的字符是比较短的，BF 算法速度很快。在使用 KMP 算法的时候，反而还需要进行预处理。

现在 C++ 的高效字符串搜索有 std::search 泛型算法。用的是 BM 算法。https://en.cppreference.com/w/cpp/algorithm/search。

此外BM算法常用于文本编辑器中的搜索匹配功能，比如 GNU grep。

Share