通过模式串的判断对KMP算法的改进

摘要

通常的模式匹配是指子串的定位操作,用定位函数Index(S, T, pos),从主串的第pos个字符起合模式的第一个字符起一次进行比较,若模式串与主串相等,则称匹配成功;函数值为和模式中第一个字符相等的字符在主串的的序号,否则匹配不成功,函数职位0.在KMP算法中,采用了next函数进行模式匹配,通过求next[j]的值大大地缩短了匹配的时间.在本文中,给出了模式串的判断算法,通过判断模式串中是否有与首位置值相同来提高匹配的效率,使得KMP算法更具有优势.