bom匹配算法？

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

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

n1 的作用是記錄字符集中的每個(gè)字符在模式中相對(duì)于最右端的最近距離， b 離最右端的為 0 ， m 為 1 ， o 為 2 ，其他沒(méi)有出現(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=pi+1 pi+1 …p4 ，相對(duì)于模式串本身而言依次向左移動(dòng)，如果子串 s 沒(méi)有匹配上，則繼續(xù)移動(dòng)子串 s ，直到匹配或者移出模式串最左端，設(shè)（匹配或移出） + 之前 子串 s 移動(dòng)的位數(shù)為 n，則有 n2[i]=m-i+n-1 ，并且令 n2[m-1]=1 。那么對(duì)于模式串 ”bomb” 來(lái)說(shuō) n2[4]={4,4,4,1} 。