摘要
在分析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.
出处
《计算机应用》
CSCD
北大核心
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)
关键词
串匹配
正文
模式
时间复杂度
string matching
text
pattern
time complexity