posts - 71, comments - 41, trackbacks - 0

字符串無回溯BM匹配算法

接著來個無回溯的，一般教科書上都是用KMP作case的，這里給個平均效率更好的Boyer-Moore Algorithm實(shí)現(xiàn)

?1

#include? < cstring >
?2

int ?BM( const ? char ? * text,? const ? char ? * pattern)
?3

{
?4

???? int ?arrShiftTable[ 256 ];
?5

???? int ?tLen? = ?strlen(text);
?6

???? int ?pLen? = ?strlen(pattern);
?7

???? int ?currPos,?tReadPos,?pReadPos;
?8

?9

???? // exclude?NUL
10

???? for ?( int ?i? = ? 1 ;?i? < ? sizeof ?arrShiftTable? / ? sizeof ?( int );?i ++ )
11

???? {
12

????????arrShiftTable[i]? = ?pLen;
13

????}
14

15

???? // exclude?the?last?char?in?pattern
16

???? for ?( int ?i? = ? 0 ;?i? < ?pLen? - ? 1 ;?i ++ )
17

???? {
18

????????arrShiftTable[pattern[i]]? = ?pLen? - ? 1 ? - ?i;
19

????}
20

21

???? for ?(currPos? = ?pLen? - ? 1 ;?currPos? < ?tLen;? /* null */ )
22

???? {
23

???????? for ?(pReadPos? = ?pLen? - ? 1 ,?tReadPos? = ?currPos;
24

????????????pReadPos? >= ? 0 ? && ?pattern[pReadPos]? == ?text[tReadPos];
25

????????????pReadPos -- ,?tReadPos -- )
26

???????????? /* null */ ;
27

28

???????? if ?(pReadPos? < ? 0 )
29

???????? {
30

???????????? return ?tReadPos? + ? 1 ;
31

????????} ?
32

???????? else
33

???????? {
34

????????????currPos? += ?arrShiftTable[text[currPos]];
35

????????}
36

37

????} // outer?for
38

39

???? return ? - 1 ;
40

}

算法原理就不細(xì)說了，有興趣可以google一下，主要思想就是從模式串的最后一個字母向前比較。此處需要使用一個跳轉(zhuǎn)表，以便查詢不匹配時模式串前進(jìn)的步數(shù)。

posted on 2006-11-16 18:03 Charles 閱讀(1057) 評論(1) 編輯收藏引用所屬分類: 面試小算法

FeedBack:

# re: 字符串無回溯BM匹配算法

2006-11-16 23:05 | 海上冰魂

汗。完全看不懂：（回復(fù) 更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。


相關(guān)文章: Integer Partition 數(shù)1的個數(shù) Fibonacci 簡單打印內(nèi)存的小玩意兒矩陣式螺旋輸出求最大公約數(shù)與最小公倍數(shù) 數(shù)內(nèi)置類型的bit數(shù) 計算Int最大最小值兩個堆棧模擬一個隊列檢測補(bǔ)碼表示

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理