Horspool即后缀搜索，也就是搜索已读入文本中是否含有模式串的后缀；对所给的字符串和模式,从右向左匹配,如果发现有一个不匹配的项,那么移动模式,使得窗口中的最后一个字符c和模式中最后一次出现的字符c对齐,然后进行下一次匹配.如下图例子:

栗子

//pSrc为t文本数组 ,pSubsrc为模式数组
 int HorspoolMatch(byte[] pSrc, int nSrcSize, byte [] pSubSrc, int nSubSrcSize)
    {
//判断如果文本数组的长度小于模式数组,直接返回-1
        if (nSubSrcSize > nSrcSize)
        {
            return -1;
        }
  //创建int数组,用于保存移动的距离,由于byte的取值范围为-128~127之间,所以只需要256长度的数组就足够了.
        int [] skip = new int[256];
//初始化距离数组,全部设置为不存在模式的情况,距离为模式的长度
        for(int i = 0; i < 256; i++)
        {
            skip[i] = nSubSrcSize;
        }
//从左到右地对模式中地字符进行距离地计算,结果只保存每一个字符最后一次出现的位置
        for(int i = 0; i < nSubSrcSize - 1; i++)
        {
            skip[pSubSrc[i]] = nSubSrcSize - i - 1;
        }

        //进行匹配
        int pos = 0;
        while(pos <= nSrcSize - nSubSrcSize)
        {
            int j = nSubSrcSize -1;
            //每有一个字符匹配j--
            while(j >= 0 && pSrc[pos + j] == pSubSrc[j])
            {
                j--;
            }
//当j<0表示模式与文本匹配
            if(j < 0 )
            {
                break;
            }
//根据窗口文本中的最后一个字符,移动模式
            pos = pos + skip[pSrc[pos + nSubSrcSize -1]];
        }
        return pos;
    }

上面的代码适用于英文字符的检索,当检索的文本中含有中文时,需要对辅助数组进行偏移,因为中文字符在转换成为byte数组时存在负数的情况.修改距离计算公式由原来的skip[pSubSrc[i]] = nSubSrcSize - i - 1;改为skip[pSubSrc[i]+127] = nSubSrcSize - i - 1;同时在对模式进行移动时也需要进行相应的修改pos = pos + skip[pSrc[pos + nSubSrcSize -1]];--->pos = pos + skip[pSrc[pos + nSubSrcSize -1]+127];

和坏字符算法的区别

坏字符算法是BM算法中的一部分,他的思路与Horspool有些相同的地方,也有不同的地方.坏字符算法所依赖的移动距离是根据坏字符的位置的,而Horspool则是依赖于窗口的最后一个字符c,当坏字符算法的坏字符出现在窗口的最后一个字符时,这时的坏字符算法就和Horspool相同.例如:

坏字符算法

引用自百度