??? 今天上課老師講了
KMP
的模式匹配算法，看了覺得很不錯，不過當
KMP
的
next
數(shù)組全為
-1
時，就退化成了樸素的模式匹配，覺得蠻郁悶的，后來自己看了
BM
匹配算法，感覺比
KMP
要好些，嘿嘿……
關于
KMP
算法，好像
Optimistic
寫了一篇文章，我在此就不說了，大家有興趣可以去看看:
??? http://m.shnenglu.com/sicheng/archive/2006/10/10/13537.html
思想：
假設給定模式串
”bomb”
和字符串
“universal_super_bomb”
，在進行匹配的時候從最后一個開始比較：
T: universal_super_bomb
P: bomb
很明顯，
e
在模式串中根本不存在，那么最優(yōu)的下一步匹配就應該是：
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=pi+1 pi+1 …p4
，相對于模式串本身而言依次向左移動，如果子串
s
沒有匹配上，則繼續(xù)移動子串
s
，直到匹配或者移出模式串最左端，設（匹配或移出）
+
之前
子串
s
移動的位數(shù)為
n
，則有
n2[i]=m-i+n-1
，并且令
n2[m-1]=1
。那么對于模式串
”bomb”
來說
n2[4]={4,4,4,1}
。（
看這里花了我好久的時間哦，明明是
C++
數(shù)據(jù)結構，里面其他地方的下標是從
0
開始，而這里卻是從
1
開始，暈死……）
接下來就是如何匹配。匹配的時候先把目標串和模式串左對齊，然后從模式串最右端開始比較，
pi
和
tj
不相等則計算
k=max(n1[(‘a(chǎn)’<=t[j]&&t[j]<=’z’)?(t[j]-‘a(chǎn)’):26],n2[i])
，并將模式
P
右移
k+i-m
位，用
pm-1
和
tj+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]
進行比較：
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]
進行比較：
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]
進行比較：
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]
進行比較：
T: universal_super_bomb
P:??????????????????????? bomb
匹配成功。
（例子有點差哦，沒有體現(xiàn)
n1
和
n2
的作用，不好意思啊，各位，原諒我吧……
偷個懶，懶得換了……）
實現(xiàn)：
再次偷懶，這次不想寫，下次寫吧，嘿嘿……
posted on 2006-10-11 20:45
Asp 閱讀(3384)
評論(3) 編輯 收藏 引用 所屬分類:
Ar!thmEt!c