| 基于前缀的BM串匹配改进算法 |
| |
| 引用本文： | 庞善臣.基于前缀的BM串匹配改进算法[J].山东科技大学学报(自然科学版),2004,23(3):46-48. |
| |
| 作者姓名： | 庞善臣 |
| |
| 作者单位： | 山东科技大学,信息科学与工程学院,山东,泰安,271019;同济大学,计算机科学与工程系,上海,200092 |
| |
| 基金项目： | 国家杰出青年科学基金资助课题(60125205) |
| |
| 摘 要： | 采用文献11]求解子串前缀的方法，给出了BM算法一个改进算法。改进算法最坏情况下的时间复杂度达到O(m*n／k)，有效地减少了字符重复比较的次数，提高了匹配效率。
|
| 关 键 词： | 串匹配 正文 模式 时间复杂度 |
| 文章编号： | 1672-3767(2004)03-0046-03 |
| 修稿时间： | 2003年12月20 |
Improved Algorithm for BM String Matching Based on Prefix Substring |
| |
| PANG Shan-chen.Improved Algorithm for BM String Matching Based on Prefix Substring[J].Journal of Shandong Univ of Sci and Technol: Nat Sci,2004,23(3):46-48. |
| |
| Authors: | PANG Shan-chen |
| |
| Institution: | PANG Shan-chen~ |
| |
| Abstract: | Using the technology for finding the longest prefix substring of pattern in 11], an improved BM-algorithm is presented. The time complexity of the improved algorithm under the worst condition is O(m*n/k),so it reduces the times of matching efficiently. |
| |
| Keywords: | string matching text pattern time complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
