摘要
KMP算法是经典的串匹配算法之一.本文首先引入刻划模式串前缀特征的集合K_j及其划分,讨论了其若干性质.然后定义函数f与next,利用f刻划了K_j的构造,由此得到了f的迭代计算方法;证明了next与f之间的关系,从而给出了KMP算法原理的形式表述和数学证明.最后,基于f的迭代计算方法以及next与f之间的关系,给出了算法描述,分析了时间复杂度.
KMP algorithm is one of classic string matching algorithms. A set Kj, for 1〈j〈m, which characterize a pattern prefix, and its partition are introduced, their some properties are discussed. Then, functions f and next are defined, the structure of Kj is described by f, a iterative computing method of f is proposed, the relationship between functions next and f is proved. Thus, mathematical principles of KMP algorithm is strictly established. Finally, the algorithm is described based on the iterative computing method of f and the relationship between functions next and f, and its complexity is analyzed.
出处
《微电子学与计算机》
CSCD
北大核心
2013年第4期30-33,共4页
Microelectronics & Computer
基金
国家自然科学基金项目(60903034
61100018
61100025
61100026)
湖北省自然科学基金项目(2011CDB069)
关键词
串匹配
KMP算法
特征集
最大值函数
复杂度分析
string matching
KMP algorithm
characteristic set
maximum value function
complexity analysis
