0001 int match ( char* P, char* T ) { //Boyer-Morre算法(简化版,只考虑Bad Character Shift) 0002 int* bc = buildBC ( P ); //预处理 0003 size_t n = strlen ( T ), i = 0; //文本串长度、与模式串首字符的对齐位置 0004 size_t m = strlen ( P ); //模式串长度 0005 while ( n >= i + m ) { //在到达最右端前,不断右移模式串(可能不止一个字符) 0006 int j = m - 1; //从模式串最末尾的字符开始 0007 while ( P[j] == T[i+j] ) //自右向左比对 0008 if ( 0 > --j ) break; 0009 if ( j < 0 ) //若极大匹配后缀 == 整个模式串,则说明已经完全匹配,故 0010 break; //返回匹配位置 0011 else //否则,根据BC表 0012 i += __max ( 1, j - bc[T[i+j]] ); //相应地移动模式串,使得T[i+j]与P[bc[T[i+j]]]对齐 0013 } 0014 delete [] bc; //销毁BC表 0015 return i; 0016 }