今天繼續昨天的話題，字符串匹配算法之 BM 算法，BM 可以說是繼 KMP 算法之後更加優秀的字符串匹配算法了，BM 是大師 Boyer-Moore 的算法傑作，所以稱 BM 算法，相比 KMP 算法效率提高了不少，在空間上 BM 算法需要一個跟匹配字符集相同的輔助空間，已存放不同的匹配字符，比 KMP 要浪費不少，但是這也是 BM 的特色，可以在不同的字符集使用，兩個字符集的話那就放一個字符集同大小的輔助空間就好，最複雜字符就很好了，目前大部分的高級語言比如 C# 都使用了 BM 及其改進算法 (AC-BM 算法)，相比 KMP 匹配兩個中文字符出現的半角結果而言，我還是偏好 BM ，雖然浪費空間，但是，實現接近低於線性的消耗，少了一個 n 以上的的匹配時間，這點也是客觀的
BM 算法還有很多衍生算法 AC-BM 算法就是一種，用數學方法進行了優化，最好情況提高了一個常數級，提高了索引利用效率，這個下次有空再寫吧 算法原理：從字符串後掃描，利用了匹配後綴和無效字符的替換原則，總體效率提高不少 算法如下，具體的算法註釋已經添加不懂的話，請留言或者跟我聯繫，我有時間會盡量解答
調試歡迎，TC 環境，GCC 下沒時間調試，改改應該沒有問題 BM 字符串匹配算法：
/*BM 字符串匹配算法 */
/*code by CG lidaren.com
* ACM yctc
*2008 12 20
*/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define LEN 256
/*LEN 使用一個 character set ASCII 編碼使用一個字節表示字符，UNICODE 要另
* 外考慮，BM 算法優勢所在 */
/*BM () BM 算法基本功能函數
* 輸入:
* char *s 匹配串
* char *p 模式串
* int index 匹配開始索引
* int post [] 輔助數組
* 返回:
* int 下一個匹配開始的索引，匹配失敗返回 - 1
*/
int BM(char *s, char *p, int index, int post[]) {
int len = strlen(s);
int i,j, next;
i = strlen (p)-1;/* 字符串長度減 1*/
j = index+strlen (p)-1;/* 第一次調用 BM () 時 index = 0，因
* 為下面的 for 循環是從模式串的末尾開始比較，所以匹配串的初始比較位
* 置應該是從開頭數模式串長度個位置開始。*/
*/
for(; i>=0; i--, j--) {
if (s [j] != p [i]){/* 第一個字符的匹配 */
break;
}
}/*for*/
if (i<0) /* 匹配完畢？*/
return 0; /* 匹配成功 */
else if(post[s[j]]>0)
/* 當出現不匹配時，查看匹配串當前位置的字符有沒有出現在模式串中 */
next = index + i - post[s[j]];
/*index 是當前的匹配串起始偏移量，i 是模式串還剩的比較字串數目，
* post [s [j]] 是所出現的第一個不匹配的字符在匹配串中的位置。
* 這樣下次比較就從匹配串中出現 s [j] 的位置開始比較
*/
else next = index + 1;
if(next > LEN-strlen(p))
return -1; /* 匹配失敗，無法進行下一次匹配 */
else
return next; /* 匹配失敗，需要下一次匹配 */
}/*BM*/
/* 測試，匹配串 和 模式串都使用小寫字符 */
int main()
{
int post [LEN]={0}; /* 輔助數組 = 字符集大小 */
char \*src="aaaabbbaababababbabb";/\*測試字符串\*/
char \*patten="aabbabb";
int i, next, index=-2, pos=0;/\*初始化索引標誌\*/
for(i=0; i
index = BM(src, patten, 0, post);/\*第一次匹配，從0位置開始,獲得NEXT\*/
while(!(index == -1 || index == 0)) /\*循環直到匹配成功\*/
{
next = index;
index = BM(src, patten, next, post);/\*下一次BM匹配\*/
}/\*while\*/
if(index == -1){ /\*faild\*/
printf("Match faildn");
}
if(index == 0){ /\* OK \*/
printf("the index is: %d.n", next);
}
return 0;
}/*main*/
網上搜索了一些關於 BM 算法的資料請參閱http://blog.chinaunix.net/u/11828/showart_242074.html 講得很詳細