一、坏字符与模式串滑动
坏字符是串S中引起匹配失败的字符，坏字符又可以分为两类：S: "abbadcababacab", T: "babac"， 串S中的字符d就是一个坏字符
对于这种情况，我们直接把模式串向后移动使其T[0]与d的下一位对其，然后从后开始进行下一轮匹配；
2. 坏字符串在模式串中，如上面例子移动后，从后往前比较，b和c不相同，而字符b在模式串T中出现，此时就把模式串移动到模式串的该字符和串的该坏字符对其，但是如果该坏字符在模式串种出现了不止一次，我们怎么移动了？这时候，为了保守起见，我们移动模式串使模式串种最右端的坏字符和串的该坏字符对其，如下：
如果按照最下面的方法移动，和最左端的字符对其，则可能会漏掉匹配项，如上图所示。
二、知道了坏字符和如何滑动模式串了，计算移动步伐step
代码的难处在遇到坏字符后该如何移动模式串，即计算移动步伐(step)。
1. 对于第一种情况，坏字符不在模式串中，直接就T[0]移动到该位置之后,
int horspool(const char *S, const char *T){
if(S==NULL || T==NULL) return -1;
int n = strlen(S);
int m = strlen(T);
int table[256] = {-1};
//记录模式串中字符出现的最右位置
for(int i=0; i<m; ++i)
table[ T[i] ] = i;
//移动步伐
int step = 0;
for(int i=0; i+m<=n; ++i){
step = 0;
//开始匹配，从右往左匹配
for( int j=m-1; j>=0; --j){
if( S[i+j] != T[j] ){
step = j-table[ S[i+j] ];
//防止原地踏步
if(step <1 ) step = 1;
//本轮匹配失败，从新位置开始比较
break;
}
}
//一轮匹配结束后，没有匹配失败的，说明匹配成功
if(step == 0) return i;
}
return -1; //匹配失败
}
字符串匹配之horspool算法,布布扣,bubuko.com
原文：http://blog.csdn.net/swagle/article/details/24269403