BM串匹配的一个改进算法  

Improved BM-algorithm for pattern matching in string

作　　者：庞善臣[1,2] 王淑栋[2] 蒋昌俊[1] 

机构地区：[1]同济大学计算机科学与工程系 [2]山东科技大学信息科学与工程学院,上海200092

出　　处：《计算机应用》2004年第12期11-13,共3页journal of Computer Applications

基　　金：国家杰出青年科学基金资助项目 (6 0 1 2 52 0 5) ;国家自然科学基金资助项目 (90 41 2 0 1 3 ) ;国家 86 3计划资助项目 (2 0 0 1AA41 3 0 2 0 ) ;上海市重点基础项目 (0 2DJ1 40 6 4);国家杰出青年科学基金 (6 0 1 2 52 0 5) ;国家 86 3计划资助项目 (2 0 0 1AA41 3 0 2 0 ) ;上海市重点基础资助项目 (0 2DJ1 40 6 4)

摘　　要：在分析BM算法和文献[12]的基础上,给出了BM串匹配的一个改进算法。该算法有以下重要的特点:1)最坏情况下,算法有效地减少了字符重复比较的次数,提高了匹配效率;2)匹配算法在二维匹配和不精确匹配中较易推广。On the basis of BM-algorithm and [12], an improved BM-algorithm was presented. The important characters of the improved BM-algorithm were stated as follows: 1) The complexity of the algorithm was reduced efficiently; 2) The matching algorithm was more easily extended to two dimensions and approximate matching.

关 键 词：串匹配 正文 模式 时间复杂度 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]