本文共 776 字，大约阅读时间需要 2 分钟。

字符串匹配

1. 字符串匹配，即在字符串 A 中查找字符串 B，将字符串 A 称为主串，字符串 B 称为模式串，n 是主串长度，m 是模式串长度；

BF 和 RK 算法

1. BF 算法，最简单，暴力的字符串匹配，在主串中，依次从起始位置 0，1，2，n-m 处，且长度为 m 的子串，和模式串进行匹配的；

   

2. BF 算法，时间复杂度是 O( n * m)，n、m 表示主串和模式串的长度，因为最多比对 n 次，而每次比对，需要对 m 个字符逐一比对，优点是实现简单，适合小规模数据，大部分场景可用；

3. RK 算法，是在 BF 算法上进行改造，因为 BF 算法，每次比对时，都需要逐一对模式串一个一个字符进行比对，RK 将这个步骤改进为分别对模式串，和要比对的字串求哈希值，首先进行哈希值比对，只有哈希值相同，才逐一比对，避免哈希冲突，不过这个算法，要求哈希值的计算非常快，且不用遍历字符串；

4. RK 算法的时间复杂度是 O( n )

BM 算法的核心思想

1. 在 BF 算法上，每次是将游标向后移动一位，与模式串进行匹配，但往往有一些规律，可以一次移动多位，这样可以跳过一些肯定不匹配的情况；

2. 例如，下面最后一个字符 c，在模式串中根本不存在，所以游标可以直接向后移动三位，直接从 aca 开始比较，不必从 bca 开始比较；

   

3. 利用 2 和其他的一些规律，使得一些显然不匹配的子串被过滤掉，减少了不必要的字符比较，提高了匹配效率，在最好情况下，BM 算法的时间复杂度是 O( n/m )；

4. BM 算法，是工程中非常常用的一种高效字符串匹配算法，广泛用户编辑器的搜索功能中；

KMP 算法

1. KMP 算法，和 BM 算法类似，核心思想，遇到不可匹配的字符的时候，希望找到一些规律，可以将模式串往后多滑动几位，跳过那些肯定不会匹配的情况，KMP 算法的时间复杂度是 O(n+m)；

转载地址：http://zpfin.baihongyu.com/