KMP算法的理论研究  

Theoretical Research of KMP Algorithm

作　　者：韩光辉[1] 曾诚[2,3] 

机构地区：[1]武汉商业服务学院信息工程系,湖北武汉430056 [2]湖北大学数学与计算机科学学院,湖北武汉430062 [3]武汉大学软件工程国家重点实验室,湖北武汉430072

出　　处：《微电子学与计算机》2013年第4期30-33,共4页Microelectronics & Computer

基　　金：国家自然科学基金项目(60903034;61100018;61100025;61100026);湖北省自然科学基金项目(2011CDB069)

摘　　要：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.

关 键 词：串匹配 KMP算法 特征集 最大值函数 复杂度分析 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]