String Matching

在字符串 A 中查找字符串 B,A 叫做主串,B 叫做模式串

BF

Brute Force,暴力匹配算法或朴素匹配算法。

思想:主串长度为 n,模式串长度为 m,在主串中,从起始位置 0、1、2 ... n-m 且长度为 m 的 n - m + 1 个子串中,看有没有和模式串匹配的。

最差时间复杂度 O(n*m),最差情况下,每次需要对比 m 个字符,需要对比 n - m + 1 次。

尽管 BF 算法的时间复杂度很高,但是实际开发中较常用,原因是:

  • 大部分情况下,模式串和主串都不太长。

  • 每次模式串与主串中的子串比较时,中途遇到不能匹配的,就能提前停止,大部分情况不会达到最差时间复杂度。

  • 思想简单,实现简单,不易出错。

RK

Rabin-Karp 算法,由两位发明者命名的。

BF 算法中,每次模式串与主串的子串比较时,都需要比较模式串的每个字符。RK 的核心思路就是计算 n - m + 1 个子串的 hash 值,然后与模式串的 hash 值比较,hash 的比较就非常快了。

但是所有子串计算 hash 值的时候还是要遍历每个子串的所有字符,此时就需要设计一个 hash 算法来优化。

核心思路是 hash 值的计算可以利用前一个子串的计算结果。比如:假设匹配的字符串的字符集只有 K 个字符,可以用 K 进制数来表示一个字符,转换为 10 进制数作为 hash 值。

时间复杂度 O(n)。

如果考虑 hash 冲突,在 hash 值相等后还需要比较原始的字符串。

BM

Boyer-Moore 算法包含两部分,坏字符规则(bad character rule)和好后缀规则(good suffix shift)。

模式串与主串的匹配过程可以看做是模式串不断在主串中往后移动。当遇到不匹配时,BF、RK 算法是模式串往后移动一位;BM 算法的本质就是寻找规则,让模式串尽可能往后多移动几位。

坏字符规则

首先是按照模式串下标从大到小倒着匹配。当发现某个字符(坏字符)无法匹配时,坏字符对应模式串中的下标为 si,然后拿这个坏字符在模式串中从后往前查找,找到下标为 xi,若没有找到 xi = -1,那么模式串就往后移动 si - xi 位。

如下例子,从后往前匹配,c 是坏字符,si = 2,xi = -1,所以模式串往后移动 3 位。移动完成后接着匹配,a 为坏字符,si = 2,xi = 0,所以模式串往后移动 2 位。

a b c a c a b d c
a b d
      a b d
          a b d

最好时间复杂度:O(n/m)。主串:aaabaaabaaab,模式串:aaaa。

问题:主串:aaaaaaaaaaa,模式串:baaa,按照刚才的算法还会后退。

好后缀规则

后缀子串:最后一个字符对齐,如 abc 的后缀子串有 c、bc。 前缀子串:起始字符对齐,如 abs 的前缀子串有 a、ab。

模式串与主串从后往前比较时,在发现坏字符时,前面已经有部分匹配了,匹配的部分叫做好后缀。如下,坏字符为 a,好后缀为 ca。

a b c a c a b d c
    d b c a

原理:模式串已经匹配好的好后缀部分记做 {u},然后好后缀在模式串中继续查找,找另一个与 {u} 匹配的 {u*}:

  • 若能找到 u{*},就将模式串滑动到 {u*} 与主串中好后缀对齐的位置。

  • 若不能找到 u{*},就查看好后缀的后缀子串是否存在与模式串的前缀子串匹配的情况,并找到最长的 {v},然后模式串滑动到 {v} 与主串中 {v} 对齐的部分。

// {u} = de,情况 1 能找到 {u*}
a b c d e f g
d e a d e
      d e a d e

// {u} = de,情况 2 不能找到 {u*},{v} = d
a b c d e f g
e a a d e
        e a a d e

分别计算好后缀和坏字符规则的滑动长度,取最长的滑动。

KMP

KMP 算法与 KM 本质一样,在模式串与主串匹配过程中,若遇到不匹配的,则寻找规律尽量使模式串多往后移动几位。

Trie 树

Trie 树,也叫字典树。专门用于处理字符串匹配的数据结构,解决在一组字符串集合中快速查找某个字符串的问题。

本质:利用字符串之间的公共前缀,将重复的前缀合并在一起。

如下图所示,根节点不包含任何信息,每个节点表示一个字符串中的字符,从根节点到红色节点的路径表示一个字符串。注意:红色节点不一定为叶子节点

// 假设字符串中只有 a~z 26个小写字母。这种存储方式比较消耗内存。
// 节点可以换成其它数据结构来节约内存,比如跳表、散列表、红黑树等
class TrieNode {
  char data;
  TrieNode children[26];
  public boolean isEndingChar = false;
}

时间复杂度:构建 Trie 树为 O(n),n 表示所有字符串长度总和,构建仅需一次;查找为 O(k),k 为需要查找字符串的长度。

适用条件

  • 字符集不能太多,不然会消耗很多内存;若节点改成其它数据结构,就会降低效率。

  • 字符串前缀重复较多。

适用场景

  • 自动不全

  • 搜索关键字提示

与散列表、红黑树比较:精确匹配适合散列表、红黑树等数据结构;前缀匹配适合 Trie 树。

例题

AC 自动机

Aho–Corasick 算法是基于 Trie 树的一种改进算法。

Last updated