一种改进的BMHS模式匹配算法

摘要

Pattern matching plays an important role in computer application. By analyzing BM, BMH, BMHS algorithm and their corresponding improved algorithms, a new improved algorithm(called DBMHS) based on BMHS is proposed. DBMHS takes full advantages of two ends string characters of pattern string, through comparing two ends character jump distance of pattern matching, jump distance is increased. The experiment results show that the improved algorithm significantly increases the jump distance of matching window, effectively improving the matching efficiency.%模式匹配在计算机应用中扮演着很重要的角色。通过分析BM，BMH和BMHS算法及相关改进算法，提出BMHS算法的改进算法(DBMHS)。该算法(DBMHS)充分利用模式串两端字符，通过比较模式串两端字符的跳转距离来实现更大距离的跳转。实验证明，改进后的算法显著增加了匹配窗口的跳转距离，有效地提高了匹配效率。