??? 今天上課老師講了 KMP 的模式匹配算法，看了覺得很不錯(cuò)，不過當(dāng) KMP 的 next 數(shù)組全為 -1 時(shí)，就退化成了樸素的模式匹配，覺得蠻郁悶的，后來自己看了 BM 匹配算法，感覺比 KMP 要好些，嘿嘿……

關(guān)于 KMP 算法，好像 Optimistic 寫了一篇文章，我在此就不說了，大家有興趣可以去看看:
??? http://www.shnenglu.com/sicheng/archive/2006/10/10/13537.html

思想：

假設(shè)給定模式串 ”bomb” 和字符串 “universal_super_bomb” ，在進(jìn)行匹配的時(shí)候從最后一個(gè)開始比較：

T: universal_super_bomb

P: bomb

很明顯， e 在模式串中根本不存在，那么最優(yōu)的下一步匹配就應(yīng)該是：

T: universal_ super _bomb

P: ??? ??bomb

這樣顯然效率就要比 KMP 高，而這就是 BM 匹配算法的思想。

?

方法：

現(xiàn)在那模式串 “bomb” 來舉例，模式串長度 m=4 。

BM 模式匹配中有 2 個(gè)數(shù)組，定一個(gè)是 n1 ，一個(gè)是 n2 。

n1 的作用是記錄字符集中的每個(gè)字符在模式中相對于最右端的最近距離， b 離最右端的為 0 ， m 為 1 ， o 為 2 ，其他沒有出現(xiàn)的則為 4 ，那么 n1[27]={4,0,4,4,4,4,4,4,4,4,4,4,1,4,2,4,4,4,4,4,4,4,4,4,4,4,4} （ ’_’ 占 n[26] ）。

n2的作用是存儲(chǔ)模式中第i個(gè)字符不等時(shí)，可以移動(dòng)的位數(shù)。
??? 考慮模式串的子串 s=p_i+1 p_i+1 …p₄ ，相對于模式串本身而言依次向左移動(dòng)，如果子串 s 沒有匹配上，則繼續(xù)移動(dòng)子串 s ，直到匹配或者移出模式串最左端，設(shè)（匹配或移出） + 之前 子串 s 移動(dòng)的位數(shù)為 n ，則有 n2[i]=m-i+n-1 ，并且令 n2[m-1]=1 。那么對于模式串 ”bomb” 來說 n2[4]={4,4,4,1} 。（ 看這里花了我好久的時(shí)間哦，明明是 C++ 數(shù)據(jù)結(jié)構(gòu)，里面其他地方的下標(biāo)是從 0 開始，而這里卻是從 1 開始，暈死……）

接下來就是如何匹配。匹配的時(shí)候先把目標(biāo)串和模式串左對齊，然后從模式串最右端開始比較， p_i 和 t_j 不相等則計(jì)算 k=max(n1[(‘a(chǎn)’<=t[j]&&t[j]<=’z’)?(t[j]-‘a(chǎn)’):26],n2[i]) ，并將模式 P 右移 k+i-m 位，用 p_m-1 和 t_j+k 繼續(xù)比較。

比如：

T: universal_super_bomb

P: bomb

p[3]!=t[3] ，那么 k=max(n1[(‘a(chǎn)’<=t[j]&&t[j]<=’z’)?(t[j]-‘a(chǎn)’):26],n2[i])=max(4,1)=4 ，則將模式串右移 k+(i+1)-m=4+4-4=4 位， j+k=3+4=7 ， p[3] 和 t[7] 進(jìn)行比較：

T: universal_super_bomb

P:???? bomb

p[3]!=t[7] ，那么 k=max(n1[(‘a(chǎn)’<=t[j]&&t[j]<=’z’)?(t[j]-‘a(chǎn)’):26],n2[i])=max(4,1)=4 ，則將模式串右移 k+(i+1)-m=4+4-4=4 位， j+k=7+4=11 ， p[3] 和 t[11] 進(jìn)行比較：

T: universal_super_bomb

P:??????? ???bomb

p[3]!=t[11] ，那么 k=max(n1[(‘a(chǎn)’<=t[j]&&t[j]<=’z’)?(t[j]-‘a(chǎn)’):26],n2[i])=max(4,1)=4 ，則將模式串右移 k+(i+1)-m=4+4-4=4 位， j+k=11+4=15 ， p[3] 和 t[15] 進(jìn)行比較：

T: universal_super_bomb

P:???????????????? bomb

p[3]!=t[15] ，那么 k=max(n1[(‘a(chǎn)’<=t[j]&&t[j]<=’z’)?(t[j]-‘a(chǎn)’):26],n2[i])=max(4,1)=4 ，則將模式串右移 k+(i+1)-m=4+4-4=4 位， j+k=15+4=11 ， p[3] 和 t[15] 進(jìn)行比較：

T: universal_super_bomb

P:??????????????????????? bomb

匹配成功。

（例子有點(diǎn)差哦，沒有體現(xiàn) n1 和 n2 的作用，不好意思啊，各位，原諒我吧…… 偷個(gè)懶，懶得換了……）

實(shí)現(xiàn)：

再次偷懶，這次不想寫，下次寫吧，嘿嘿……