Python2.5 的实现中有一个字符串匹配算法，在 s 中查找 p 是否存在，s 的长度为 n，p 的长度为 m。这个算法符合以下要求：

• 任何情况下都要比 brute-force 算法快
• O(1) 的空间，O(m) 的初始化复杂度
• O(n/m) 的查找复杂度
• 最坏情况下不能比 O(nm) 时间复杂度差
• 实现简单，对于实际中的查找大部分表现良好，最坏情况出现概率小

标准的字符串查找算法不满足这些要求，KMP 的时间复杂度为 O(m+n)(初始化 O(m) 加第二部分 O(n)，Boyer-Moore 和其变形要求额外的空间，Python2.5 里面增加了这个结合了 Boyer-Moore 和 Sunday 的思想的变形实现。来看看这是怎么个神奇的算法，KMP 的思想是在每一次不匹配的情况下尽量的向右边移动，所以计算一个 Next 的移动下标数组。如果不匹配，最理想的情况下是向右边移动多长？应该是 m，这样就能尽量减少对比的次数。所以每次比较的时候先比较 p 的最后一个字符，比如 s=”aaaaaaad”，p=”aae”，如果从 s 的开头查找，只要发现第 3 个和 p 的第三个不一样，移动指标，移动多少？如果发现没有 e，最长能移动 p 的长度，就是 3。如果最后一个不匹配并且 s[i+m] 不是 p 中的字符就移动 m，否则移动 1。这里有两个问题：

如何知道 s 中的某一个字符是否是 p 中的一部分？
如何尽量移动 m 而不出现少找的情况？

第一个问题，可以用某个存储空间存下是否有 p 中的某个字符出现过，方便以后查找。Hash 的思想，但是这里字符串查找里面再弄个 Hash 太无语了吧。一个简单的 Bloom-filter，这里是这样实现的。

/*计算 mask*/ 
mlast = m-1;
for (mask = i = 0; i <= mlast; i++) {
    mask |= (1 << (p[i] & 0x1F));
}

/*判断 s[i] 不是 p 中的一个字符串*/ 
if(!(mask & (1 << (s[i] & 0x1F))))
     printf("s[i] is not in pattern");
else 
     printf("s[i] is in pattern");

其实我们是要判断一个 s 中的一个字符串没有出现在 p 中，取低 5 位不是可能产生冲突么？产生冲突也没问题，就像一个 Hash 只要一个元素算出来的 Key 指定的 slot 没元素不就能确定这个元素不在里面了么。

第二个问题，有些巧妙。上面那个例子是因为 s 的最后一个字符没被匹配，所以能移动 m 的长度。如果这个例子 s=”aaacaaaacaa”，p=”aacaa”，第 5 个位置都为 a，最后一个匹配，但是 s 里面前几个其实不为 aacaa，所以需要移动，但是移动多少呢？如果移动 p 的长度，那从第 2 个位置开始的 aacaa 就没被检查到。所以需要一个变量记录在每次最后一个字母匹配的情况下向右移动的合理偏移量，在这里为 skip，初始化的时候计算出来，这最偏移量其实是计算的最小偏移量，就是移动 skip 个位置到第一个 s[m-1] 的位置。整个实现既节省空间又速度快，强大。

具体实现如下：

//如果 mode 为 FAST_COUNT，则查找 pattern 出现的次数
#define FAST_COUNT 1

int fastsearch(const char* s, size_t n,
           const char* p, size_t m,
           int mode)
{
    long mask;
    size_t skip, count = 0;
    size_t i, j, mlast, w;

    w = n - m;

    if (w < 0)
        return -1;

    /* 如果 m=1，特例，扫描一遍解决*/ 
    if (m <= 1) {
        if (m <= 0)
            return -1;
        if (mode == FAST_COUNT) {
            for (i = 0; i < n; i++)
                if (s[i] == p[0])
                    count++;
            return count;
        } else {
            for (i = 0; i < n; i++)
                if (s[i] == p[0])
                    return i;
        }
        return -1;
    }

    mlast = m - 1;

    skip = mlast - 1;
    /*计算 mask*/ 
    for (mask = i = 0; i < mlast; i++) {
        mask |= (1 << (p[i] & 0x1F));
        if (p[i] == p[mlast])
            skip = mlast - i - 1;
    }
    mask |= (1 << (p[mlast] & 0x1F));

    for (i = 0; i <= w; i++) {
        if (s[i+m-1] == p[m-1]) {//pattern 末尾匹配
            /* candidate match */ 
            for (j = 0; j < mlast; j++)
                if (s[i+j] != p[j])
                    break;
            if (j == mlast) {//一个匹配成功
                if (mode != FAST_COUNT)
                    return i;
                count++;
                i = i + mlast;
                continue;
            }
            /*移动多少？,根据 mask*/ 
            if (!(mask & (1 << (s[i+m] & 0x1F))))
                i = i + m;
            else 
                i = i + skip;
        } else {
            /* skip: check if next character is part of pattern */ 
            if (!(mask & (1 << (s[i+m] & 0x1F))))
                i = i + m;
        }
    }

    if (mode != FAST_COUNT)
        return -1;
    return count;
}