(((silence)))

传说kmp算法很伟大,但我更喜欢Shift-And算法:

template <class Output_Function>
size_t Shift_And(const char* source,const char* to_find,Output_Function out){
/**
 * find to_find in source, out(where_to_find_occured);
 * return the tatol occurence's account
 */
    size_t m=strlen(to_find);
    size_t occured=0;
    if (n<m) return 0;
    const int mask_len=m/64+1;
    const int last_section_len=m%64;

    __int64 mask[128][mask_len]; //如果你的编译器不支持VLA(变量长数组), 自己改改吧
    for(int i=0;i<mask_len;++i){
        for(int j=0;j<128;++j){
            mask[j][i]=0;
        }
    }
    for(size_t j=0;j<m;++j){
        mask[static_cast<int>(to_find[j])][j/64]|=1<<(j%64);
    }
    __int64 D[mask_len];
    for(int i=0;i<mask_len;++i){
        D[i]=0;
    }
    for(size_t pos=0;source[pos];++pos){
        for(int i=mask_len-1;i>=1;--i){
            D[i]<<=1;
            D[i]|=D[i-1]>>63;
            D[i]&=mask[static_cast<int>(to_find[pos])][i];
        }
        D[0]<<=1;
        D[0]|=1;
        D[0]&=mask[static_cast<int>(source[pos])][0];
        if (D[mask_len-1]>>(last_section_len-1)){
            out(pos-m+1);
            ++occured;
        }
    }
    return occured;
}

如果不想处理每个出现的地方, 只想知道指定字符串出现了几次, 最简单,不需要改动的方法是使用这个函数作为第三个参数:
void noop(...){
// No operation, may be useful for strange reasons
}

复杂度: 当需要查找的字符串长度在一个到几个机器字之间时, 查找一个或全部子串, 时间复杂度总是O(n).
而且这个算法是很容易扩展的, 比如在一个字符串里搜索多个子串, 忽略大小写, 等等等等, 懒得去做了.