0001 int match ( char* P, char* T ) { //Boyer-Morre算法(完全版,兼顾Bad Character与Good Suffix) 0002 int* bc = buildBC ( P ); int* gs = buildGS ( P ); //构造BC表和GS表 0003 size_t i = 0; //模式串相对于文本串的起始位置(初始时与文本串左对齐) 0004 while ( strlen ( T ) >= i + strlen ( P ) ) { //不断右移(距离可能不止一个字符)模式串 0005 int j = strlen ( P ) - 1; //从模式串最末尾的字符开始 0006 while ( P[j] == T[i + j] ) //自右向左比对 0007 if ( 0 > --j ) break; 0008 if ( 0 > j ) //若极大匹配后缀 == 整个模式串(说明已经完全匹配) 0009 break; //返回匹配位置 0010 else //否则,适当地移动模式串 0011 i += __max ( gs[j], j - bc[ T[i + j] ] ); //位移量根据BC表和GS表选择大者 0012 } 0013 delete [] gs; delete [] bc; //销毁GS表和BC表 0014 return i; 0015 }