boyermoore算法的sample程序TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind){//// 声明：// 该段代码只是BoyerMoore(名字也许不准确)的基本思想，当// 然不是最优的，具体完善工作就留给你自己乐！嘻嘻。// 该算法的本质就是从字符串的右端而不是左端开始比较，这// 样，当查询不匹配时才有可能直接跃过多个字符（最多可以跃过// strlen(sFind)个字符），如果最右边的字符匹配则回溯。比如：//// pain// ^
这是第一次比较n和空格比// The rain in SpainThe rain in Spain//// pain//
^
这是第二次比较，好爽呀！// The rain in SpainThe rain in Spain//// 当然，这样比较会产生一些问题，比如：////
pain//
^
（图1）// The rain in SpainThe rain in Spain//// 如果比较到这儿，大家都会看到，只需再向后移到两个字符// 就匹配成功了，但如果接下去还按上面的方法跳strlen(sFind)的// 话，就会错过一次匹配！！！！！////
pain//
^// The rain in SpainThe rain in Spain//// 怎么办？当然可以解决！大家回头看图1，当时a是pain的子// 串，说明有可能在不移动strlen(sFind)的跨度就匹配成功，那就// 人为地给它匹配成功的机会嘛！串一下pain串，直接让两个a对齐// 再做比较！呵呵，如果要比较的字符不是pain的子串，当然就可// 以直接跨过strlen(sFind)个字符了！不知我说明白没？////// 查询串的长度int nLenOfFind = lstrlen(sFind);// 被查询串的长度int nLenOfSrc = lstrlen(sSrc);// 指向查询串最后一个字符的指针TCHAR * pEndOfFind = sFind + nLenOfFind -1;// 指向被查询串最后一个字符的指针TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1; // 在比较过程中要用到的两个指针TCHAR * pSrc = sSrc;TCHAR * pFind;// 总不能一直让它比较到win.com文件的地址去吧？嘻嘻！while ( pSrc = sFind ) {
// TNND，白废功夫比了！看看需要向右移动几个
// 字符吧（如果说从右到左是本算法的核心，则
// 判断向右移几个字符则是本算法的技巧）。
if ( *pSrc != *pFind ) {
// 被查询串的当前字符是否在查询串里？
TCHAR * p = strrchr( sFind, *pSrc );
// 没在，直接移lstrlen(sFind)个字符
if ( NULL == p )
nMoveRightSrc = nLenOfFind;
else
// 哇塞！真的在，那就只需...
nMoveRightSrc = pEndOfFind - p;
break;
}
// 哈！又匹配成功了一个！接着向左回溯...
pFind --;
pSrc --;
}
// 如果在上面的while循环里每一次比较都匹配了
// 那就对了呗！告诉用户找到了
if ( pFind = 0; --i) {
if (i > g && suff[i + m - 1 - f] = 0 && x[g] == x[g + m - 1 - f])
--g;
suff = f - g;
} }} void preBmGs(char *x, int m, int bmGs[]) { int i, j, suff[XSIZE];
suffixes(x, m, suff);
for (i = 0; i = -1; --i)
if (i == -1 || suff == i + 1)
for (; j = 0 && x == y[i + j]; --i);
if (i < 0) {
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs, bmBc[y[i + j]] - m + 1 + i); }}参考资料：http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140
已赞过已踩过<
|
