posts - 71, comments - 41, trackbacks - 0

字符串無回溯BM匹配算法

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

#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

???? // exclude?NUL
10

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

???? {
12

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

????}
14

???? // 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

???? 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

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

???????? {
30

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

????????} ?
32

???????? else
33

???????? {
34

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

????????}
36

????} // outer?for
38

???? return ? - 1 ;
40

}

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

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

FeedBack:

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

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

汗。完全看不懂：（回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

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

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

2006年11月

日

一

二

三

四

五

六

決定開始寫工作日記，記錄一下自己的軌跡...

常用鏈接

留言簿(4)

隨筆分類(70)

隨筆檔案(71)

charles推薦訪問

Code Project
Linux Journal
Linux man pages
Single UNIX Specification
電子書1
電子書2
電子書3

常用鏈接

留言簿(4)

隨筆分類(70)

隨筆檔案(71)

charles推薦訪問

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜