posts - 71, comments - 41, trackbacks - 0

字符串無(wú)回溯BM匹配算法

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

#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

}

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

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

FeedBack:

# re: 字符串無(wú)回溯BM匹配算法

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

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

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

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

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

2006年11月

日

一

二

三

四

五

六

決定開(kāi)始寫(xiě)工作日記，記錄一下自己的軌跡...

常用鏈接

留言簿(4)

隨筆分類(lèi)(70)

隨筆檔案(71)

charles推薦訪問(wèn)

Code Project
Linux Journal
Linux man pages
Single UNIX Specification
電子書(shū)1
電子書(shū)2
電子書(shū)3

常用鏈接

留言簿(4)

隨筆分類(lèi)(70)

隨筆檔案(71)

charles推薦訪問(wèn)

搜索

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜