boyermoore算法
❶ 字符串匹配算法
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 <= pEndOfSrc ) {
// 每次匹配都是从右向左，这是本算法的核心。
pFind = pEndOfFind;
// 如果比较不成功，被查询串指针将向右串的字符数
int nMoveRightSrc;
// 比较被查询串的当前字符是否和查询串的最右边字
// 符匹配，如果匹配则回溯比较，如果全匹配了，该
// 干什么，我就不用说了吧？:-)
while ( pFind >= 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 < sFind )
return ( pSrc + 1 );
// 没匹配成功，nMoveRightSrc上面已经算好了
// 直接用就可以了。
pSrc += nMoveRightSrc;
}
// 程序运行到这儿肯定是没指望了！
return NULL;
}
行了，函数写完了，我们可以试一下了！
void CTNNDDlg::OnButton1()
{
TCHAR sSrc[] = "The rain in Spain";
TCHAR sFind[]= "pain";
TCHAR * pFound = BoyerMooreSearch( sSrc, sFind );
if ( pFound )
MessageBox(pFound);
else
MessageBox("没找到");
}
//另外一个
void preBmBc(char *x, int m, int bmBc[]) {
int i;
for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;
suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}
void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];
suffixes(x, m, suff);
for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}
void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);
/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}
❷ ACwumanber优缺点
哈希冲突严重、匹配效率好。
WuManber利用了Boyer-Moore的思路，将该算法拓展到多模式匹配。第一步要算出所有模式串上的最小长度m，然后先考虑每个模式串的前m个字符。如此所有模式串长度都一样了。
AC自动机中，转移的最小单位是一个字符。也就是说，匹配后只能移动一个字符，复杂度是线性的O(n)。然而线性并非最快，Boyer-Moore算法在匹配后可以跳过多个字符，比线性还快。据说在实践中，利用Boyer-Moore优化的AC自动机总是更快。
❸ bm是什么意思
BM是一种匹配算法。
BM算法被认为是亚线性串匹配算法，它在最坏情况下找到模式所有出现的时间复杂度为O(mn)，在最好情况下执行匹配找到模式所有出现的时间复杂度为O(n/m)。
BM算法主要思想描述如下：
模式字符串的匹配顺序是从右向左:
1、首先将P和T对齐，即p和t对齐；
2、然后匹配从模式字符串P的最右端字符开始，即判断p[m]和t[m]是否匹配：
如果匹配成功，则向左移动判断p[m-1]和t[m-1]是否匹配，如此循环下去；如果匹配不成功，则进行字符串滑移。
BM算法的原理：
不同于朴素模式（brute-force search）的逐个字符对比，Boyer-Moore充分使用预处理 P的信息来尽可能跳过更多的字符。通常，我们比较一个字符串都是从首字母开始，逐个比较下去。一旦发现有不同的字符，就需要从头开始进行下一次比较。
这样，就需要将字串中的所有字符一一比较。Boyer-Moore算法的关键在于，当 P的最后一个字符被比较完成后，我们可以决定跳过一个或更多个字符。如果最后一个字符不匹配，那么就没必要继续比较前一个字符。
如果最后一个字符未在 P中出现，那么我们可以直接跳过 T的n个字符，比较接下来的n个字符，n为 P的长度（见定义）。
如果最后一个字符出现在 P中，那么跳过的字符数需要进行计算（也就是将 P整体往后移），然后继续前面的步骤来比较。通过这种字符的移动方式来代替逐个比较是这个算法如此高效的关键所在。
❹ 字符串匹配算法是怎么算的
这是一个毕业老师出的字符串的算法的题目！这是答案 可以参考一下！ 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 <= pEndOfSrc ) { // 每次匹配都是从右向左，这是本算法的核心。 pFind = pEndOfFind; // 如果比较不成功，被查询串指针将向右串的字符数 int nMoveRightSrc; // 比较被查询串的当前字符是否和查询串的最右边字 // 符匹配，如果匹配则回溯比较，如果全匹配了，该 // 干什么，我就不用说了吧？:-) while ( pFind >= 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 < sFind ) return ( pSrc + 1 ); // 没匹配成功，nMoveRightSrc上面已经算好了 // 直接用就可以了。 pSrc += nMoveRightSrc; } // 程序运行到这儿肯定是没指望了！ return NULL; } 行了，函数写完了，我们可以试一下了！ void CTNNDDlg::OnButton1() { TCHAR sSrc[] = "The rain in Spain"; TCHAR sFind[]= "pain"; TCHAR * pFound = BoyerMooreSearch( sSrc, sFind ); if ( pFound ) MessageBox(pFound); else MessageBox("没找到"); } //另外一个 void preBmBc(char *x, int m, int bmBc[]) { int i; for (i = 0; i < ASIZE; ++i) bmBc[i] = m; for (i = 0; i < m - 1; ++i) bmBc[x[i]] = m - i - 1; } void suffixes(char *x, int m, int *suff) { int f, g, i; suff[m - 1] = m; g = m - 1; for (i = m - 2; i >= 0; --i) { if (i > g && suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; } } } void preBmGs(char *x, int m, int bmGs[]) { int i, j, suff[XSIZE]; suffixes(x, m, suff); for (i = 0; i < m; ++i) bmGs[i] = m; j = 0; for (i = m - 1; i >= -1; --i) if (i == -1 || suff[i] == i + 1) for (; j < m - 1 - i; ++j) if (bmGs[j] == m) bmGs[j] = m - 1 - i; for (i = 0; i <= m - 2; ++i) bmGs[m - 1 - suff[i]] = m - 1 - i; } void BM(char *x, int m, char *y, int n) { int i, j, bmGs[XSIZE], bmBc[ASIZE]; /* Preprocessing */ preBmGs(x, m, bmGs); preBmBc(x, m, bmBc); /* Searching */ j = 0; while (j <= n - m) { for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i); if (i < 0) { OUTPUT(j); j += bmGs[0]; } else j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i); } }
❺ 【算法笔记】字符串匹配
BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法：
主串和模式串：
在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m
我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。
BF 算法的时间复杂度是 O(n*m)
等价于
比如匹配Google 和Goo 是最好时间复杂度，匹配Google 和ble是匹配失败的最好时间复杂度。
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特—莫里斯—普拉特算法。KMP算法主要分为两个步骤：字符串的自我匹配，目标串和模式串之间的匹配。
看来网上很多的文章，感觉很多的都没有说清楚，这里直接复制阮一峰的内容，讲的很清晰
内容来自 http://www.ruanyifeng.com/blog/
首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。
因为B与A不匹配，搜索词再往后移。
就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。
接着比较字符串和搜索词的下一个字符，还是相同。
直到字符串有一个字符，与搜索词对应的字符不相同为止。
这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。
一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。
怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。
已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：
因为 6 - 2 等于4，所以将搜索词向后移动4位。
因为空格与C不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。
因为空格与A不匹配，继续后移一位。
逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。
下面介绍《部分匹配表》是如何产生的。
首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，
"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。
BM（Boyer-Moore）算法。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是着名的KMP 算法的 3 到 4 倍。
BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）
未完待续
参考文章：
字符串匹配的Boyer-Moore算法