常用字符串匹配算法简介

背景

字符串模式匹配是常见的算法之一，在实际生活中有较高的使用频率，特别是在当下的互联网服务中，经常用于游戏角色名检查、论坛发帖、直播弹幕、分类打标签、入侵检测等场景。字符串模式匹配又分为单模匹配和多模匹配，区别在于单模匹配是搜索一个模式串，多模式匹配是搜索多个模式串。由于无数大佬前赴后继的投入到模式匹配算法的研究中，时至今日，又有大量成熟的匹配算法，这里姜维大家简要介绍一些，可以根据自身业务需要选用。

单模匹配算法

朴素算法

朴素算法又称暴力匹配，是最简单的字符串匹配算法，也是人们接触得最多的字符串匹配算法。总结起来就是几点：无需预处理，写起来简单，跑起来慢，时间复杂度是O((n - m + 1) * m)。

# Strings s1, s2
# s1: input string, length = n
# s2: pattern, length = m
n, m = len(s1), len(s2)
for i in range(n - m):
    if s1[i:i + m] == s2:
        # do something if match

Rabin-Karp算法

Rabin-Karp字符串匹配算法和前面介绍的朴素算法类似，也是对应每一个字符进行比较，不同的是Rabin-Karp采用了把字符进行预处理，也就是使用hash函数分别对输入串的子串和模式串分别hash，然后比较。预处理复杂度是 O(m)，匹配时间复杂度为 O((n - m + 1) * m)，既然与朴素算法的匹配时间一样，而且还多了一些预处理时间，那为什么我们还要学习这个算法呢？

虽然Rain-Karp在最坏的情况下与朴素的世间复杂度一样，但是实际应用中往往比朴素算法快很多。而且该算法的 期望匹配时间是O(n + m)(参照《算法导论》)

在朴素算法中，我们需要挨个比较所有字符，才知道目标字符串中是否包含子串。为了避免挨个字符对目标字符串和子串进行比较，Rabin-Karp算法会先尝试一下二者的hash值判断二者是否相等，可以显著提升效率

Rabin-Karp算法的思想：

假设模式串的长度为m,目标字符串的长度为n（n > m）

计算模式串的hash值

计算目标字符串中每个长度为m的子串的hash值（共需要计算N-M+1次）

比较hash值

如果hash值不同，字符串必然不匹配，如果hash值相同，还需要使用朴素算法再次判断来排除hash冲突的干扰

为了快速的计算出目标字符串中每一个子串的hash值，Rabin-Karp算法并不是对目标字符串的 每一个长度为m的子串都重新计算hash值，而是在前几个字串的基础之上， 计算下一个子串的hash值，这就加快了hash之的计算速度，将朴素算法中的内循环的世间复杂度从O(m)将到了O(1)。

关于hash函数的详细内容，可以参考《算法导论》

# Strings s1, s2
# s1: input string, length = n
# s2: pattern, length = m
# hash is a hash function
n, m = len(s1), len(s2)
hash_pattern = hash(s2)
for i in range(n - m):
    if hash(s1[i:i + m]) == hash_pattern:
        # do something if match
        # if s1[i:i + m] == hash_pattern

KMP算法

KMP算法的思想就是，当子串与模式串不匹配时，其实你已经知道了前面已经匹配成功那一部分的字符（包括子串与模式串），因此可以确定下一步从哪里开始，从而避免重新检查先前匹配的字符。

算法分为两个部分，第一部分是在预处理阶段处理模式串，构建next数组，复杂度为O(m)，第二部分就是匹配过程了，复杂度是 O(m + n)。

构建next数组的思想是，例如我们在模式串的k位置不匹配了，那么模式串的k - 1之前的位置还是都匹配的，那么我们要找一个k之前的新位置new_k，对于new_k - 1之前的位置都匹配。简单点说就是返回上一个能匹配的状态。

# Strings s1, s2
# s1: input string, length = n
# s2: pattern, length = m

# build next array
next = [-1 for i in range(m)]
for i in range(1, m):
    k = next[i - 1]
    while k != -1 and s2[k] != s2[i - 1]:
        k = next[k]
    next[i] = k + 1

# do match
i, j = 0, 0
while i < n and j < m:
    if s1[i] == s2[j]:
        i += 1
        j += 1
    else:
        if next[j] >= 0:
            j = next[j]
        else:
            j, i = 0, i + 1
        if j == m:
            # do something if match

BM算法

BM算法相对经典的KMP字符串匹配算法，效率更好。在模式串长度大的时候效率更高。算法需要对模式串进行预处理，处理过后，在搜索过程中就可以最大减少字符比较次数，以此提高效率。BM算法主要三个特点：从模式串最右开始进行匹配；坏字符表；好后缀表。基本思路就是从右往左进行字符匹配，遇到不匹配的字符后从坏字符表和好后缀表找一个最大的右移值，将模式串右移继续匹配。

算法分为两个阶段：预处理阶段和搜索阶段。

预处理阶段时间复杂度空间复杂度均为O(m + σ)。m是模式长度，σ是字符集大小，一般考虑为单字节8位共256种。

搜索阶段时间复杂度O(m * n)。

当模式串是非周期性的，最坏情况下需要做3n次字符比较，n是文本长度。

最好情况下性能为O(n / m)

坏字符算法：

不匹配的字符被称为坏字符，当字符不匹配时，遇到坏字符的后移次数为坏字符在模式串里的位置减去模式串中上一次在模式串中出现的位置，由两种情况汇总得到：

若不匹配的字符不存在于模式串内，那么直接将模式串移动到该字符后

若不匹配的字符存在于模式串内，那么后移模式串，直到模式串的某个字符与该字符匹配

好后缀规则：

连续可以匹配的后缀被成为好后缀，当好后缀存在，移动次数为好后缀的位置减去模式串中上一次好后缀的位置。

# Strings s1, s2
# s1: input string, length = n
# s2: pattern, length = m
# 这里这个 256 这个 magic number 是字符的最大数量
# bm_bad_ch 为字符字模式串中的最右边的位置
bm_bad_ch = [m for i in range(256)]
for i in range(m):
    bm_bad_ch[ord(s2[i])] = i
# suffix[i] 为以 i 为边界，可以与模式串后缀匹配的最大长度
suffix = [0 for i in range(m)]
suffix[m - 1] = m
for i in range(m - 2, -1, -1):
    k = i
    while k >= 0 and s2[k] == s2[m - 1 - i + k]:
        k -= 1
    suffix[i] = i - k
# 对于没有匹配到的情况
bm_good_suffix = [m for i in range(m)]
j = 0
for i in range(m - 1, -1, -1):
    if suffix[i] == i + 1:
        # 后缀没有完全匹配，找到一个最大前缀
        while j < m - 1 - i:
            if bm_good_suffix[j] == m:
                bm_good_suffix[j] = m - 1 - i
            j += 1
# 对于直接能匹配好后缀的情况
for i in range(m - 1):
    bm_good_suffix[m - 1 - suffix[i]] = m - 1 - i
# 开始 Boyer–Moore 匹配
i, j = 0, 0
while j <= n - m:
    i = m - 1
    while s1[i + j] == s2[i]:
        i -= 1
        if i < 0:
            break
    if i < 0:
        # do something if match
        j += bm_good_suffix[0]
    else:
        j += max(bm_good_suffix[i], bm_bad_ch[s1[i + j]])

多模式匹配

多模匹配是用多个模式串来匹配一个输入串，但并不是简单的单模匹配的叠加，多个模式串直接可能存在某些匹配联系，可以利用他们之间的匹配关系进一步加速匹配。

AC自动机

AC自动机和KMP的基本思想一致，在不匹配时，模式串上的指针不会直接跳到最初，也是和KMP思想一样寻找上一个能匹配的状态。

AC自动机的预处理复杂度为O(m + k)，其中k为各模式串的总长度，搜索复杂度为O(n + m + z)，z 代表模式串在输入串中出现的次数。

AC自动机的算法主要分为三个步骤：构造一个 Trie 树、构造失败指针和进行匹配。

AC算法大体上分为三步：

1、构建Trie前缀搜索树，并标注结束节点

2、设置每个节点的失配跳转(fail指针)并收集每个节点的所有匹配模式串

3、对输入串进行一次遍历，对于每个字符（字节）都去敏感词树型结构中，从当前结点位置开始匹配。

如果匹配成功，则当前结点，下移到对应的结点。如果当前结点为“结束节点”，则表示匹配成功；

如果匹配失败，则当前结点，跳转到该结点的失败结点，继续匹配，直到匹配成功或当前结点为根结点；

参考资料：

浅谈字符串匹配