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;
}