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

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

思想：

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

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 個數(shù)組，定一個是 n1 ，一個是 n2 。

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

接下來就是如何匹配。匹配的時候先把目標(biāo)串和模式串左對齊，然后從模式串最右端開始比較， p_i 和 t_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 的作用，不好意思啊，各位，原諒我吧…… 偷個懶，懶得換了……）

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

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