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演算法