论文研究基于KMP算法的改进算法KMPP.pdf

KMP算法和BM算法是经典的单模式匹配算法，但KMP算法中文本指针[i]每次只能移动一个字符，整体的匹配效率并不高，结合KMP算法和BM算法的优点提出一种改进算法（KMPP）。算法的思想是模式串与文本在[j]处不匹配时，预算出模式串移动[next[j]]后末字符在文本中的位置，当该位置的文本字符与末字符不匹配时，则用该字符进行坏字符匹配，这两步的跳跃距离就是文本指针[i]移动的距离，从而使指针[i]每次移动的距离达到最大。实验结果表明，该算法匹配次数远低于KMP算法的匹配次数，提高了模式匹配的效率。