最近面试阿里，第一个算法题就是字符串匹配算法，当时一脸懵逼，连朴素字符串匹配算法都不知道，面试官还问我有没有深入了解Python语言的字符串怎么查找的，顿时戳中痛点，想想自己学Python真的还是太浅了。于是就去把字符串匹配算法全学了一遍，有
brute-force算法、Rabin-Karp算法、有限自动机算法、KMP算法、
Boyer-Moore算法、Horspool算法还有Sunday算法等等。然后再去看了一下Python的字符串查找算法，链接地址为
https://github.com/python/cpython/blob/master/Objects/stringlib/fastsearch.h
该算法广泛用于
find、
index、
split、
replace、
__contains__(in关键字的实现函数)等函数中
。
在看下面之前，我假设读者知道什么是Horspool和Sunday算法了，我把这两个算法的Python实现贴出来，非常简单
#coding=utf-8
'''Horspool字符串匹配算法
预处理时间复杂度时间为O(m)，最快时间复杂度为O(n/m)
匹配时间快于Boyer-Moore算法
'''
def horspool_search(T, P):
n, m = len(T), len(P)
shift = [m for i in range(256)]
for i in range(m-1):
shift[ord(P[i])] = m - i - 1
# 跟朴素算法的区别就在于步长
i = 0
while i < n-m+1:
for j in range(m):
if T[j+i] != P[j]:
break
else:
return i
i += shift[ord(T[i+m-1])]
return -1#coding=utf-8
'''SUNDAY字符串匹配算法
预处理时间复杂度时间为O(m)，最快时间复杂度为O(n/m)
匹配时间快于Boyer-Moore算法
'''
def sunday_search(T, P):
n, m = len(T), len(P)
shift = [m+1 for i in range(256)]
for i in range(m):
shift[ord(P[i])] = m - i
# 跟朴素算法的区别就在于步长
i = 0
while i < n-m+1:
for j in range(m):
if T[j+i] != P[j]:
break
else:
return i
if i+m < n:
i += shift[ord(T[i+m])]
else:
return -1
再来看Python的快速匹配算法，上面链接里的代码太多，因为考虑了多种情况，我们只看FASTSEARCH部分，抽取出来
#define STRINGLIB_BLOOM_WIDTH 32
/* 用于记录数组中存在的元素 */
#define STRINGLIB_BLOOM_ADD(mask, ch) \
((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH - 1)))))
/* 判断字符是否在数组中 */
#define STRINGLIB_BLOOM(mask, ch) \
((mask & (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH - 1)))))
int fast_search(char *s, char *p) {
int n = strlen(s);
int m = strlen(p);
int w = n - m;
int mlast = m - 1;
int skip = mlast - 1;
int mask = 0;
int i, j;
const char *ss = s + m - 1;
const char *pp = p + m - 1;
/* create compressed boyer-moore delta 1 table */
/* process pattern[:-1] */
for (i = 0; i < mlast; i++) {
STRINGLIB_BLOOM_ADD(mask, p[i]);
if (p[i] == p[mlast])
skip = mlast - i - 1;
}
/* process pattern[-1] outside the loop */
STRINGLIB_BLOOM_ADD(mask, p[mlast]);
for (i = 0; i <= w; i++) {
/* note: using mlast in the skip path slows things down on x86 */
if (ss[i] == pp[0]) {
/* candidate match */
/* 因为已经判断字符串和模式串的最后一位相等 */
for (j = 0; j < mlast; j++)
if (s[i + j] != p[j])
break;
if (j == mlast) {
/* got a match! */
return i;
}
/* miss: check if next character is part of pattern */
if (!STRINGLIB_BLOOM(mask, ss[i + 1]))
i = i + m;
else
i = i + skip;
} else {
/* skip: check if next character is part of pattern */
if (!STRINGLIB_BLOOM(mask, ss[i + 1]))
i = i + m;
}
}
return -1;
}
这个快速匹配算法被称为BMHBNFS算法，之所以取这个名字，是因为它是
Boyer-Moore, Horspool, Sunday, Bloom Filter几种算法的集大成者，我第一次看到这算法时感觉牛逼到爆，本来Horspool和Sunday已经算字符串匹配算法中的佼佼者了（最快时间复杂度为O(n/m)），居然还有这么一种算法。
BMHBNFS算法的原理可以用简单的代码来演示
def find(s, p):
# find first occurrence of p in s
n = len(s)
m = len(p)
# skip是把离p[m-1]最近且字符相同的字符移到m-1位需要跳过的步数-1
skip = delta1(p)[p[m-1]]
i = 0
while i <= n-m:
if s[i+m-1] == p[m-1]: # (boyer-moore)
# potential match
if s[i:i+m-1] == p[:m-1]:
return i
if s[i+m] not in p:
i = i + m + 1 # (sunday)
else:
i = i + skip # (horspool)
else:
# skip
if s[i+m] not in p:
i = i + m + 1 # (sunday)
else:
i = i + 1
return -1 # not found
作者当时在设计这个算法时考虑了如下几点限制条件：
-
在任何测试用例下都要比
brute-force算法快
-
低预处理开销、不需要动态分配数组，也就是预处理时间复杂度为O(m)、空间复杂度为O(1)
-
在较好的情况下，线性搜索时间复杂度为O(n/m)
-
在最差的情况下也不会比现有算法的时间复杂度(O(nm))高
-
在8bits、16bits字符串或者32bits Unicode字符串中表现良好
-
在现实生活中的搜索中能够表现良好，很少出现最差情况
-
实现简单
有这么多限制，可想而知多牛逼，该算法的巧妙之处在于使用
Bloom filter数据结构使得算法
不再依赖字母表的大小，
空间复杂度降为O(1)，当然这样会导致处理起来比Horspool和Sunday算法复杂一点