【摘要】 KMP算法是经典的串匹配算法之一.本文首先引入刻划模式串前缀特征的集合K_j及其划分,讨论了其若干性质.然后定义函数f与next,利用f刻划了K_j的构造,由此得到了f的迭代计算方法;证明了next与f之间的关系,从而给出了KMP算法原理的形式表述和数学证明.最后,基于f的迭代计算方法以及next与f之间的关系,给出了算法描述,分析了时间复杂度.更多还原

【Abstract】 KMP algorithm is one of classic string matching algorithms.A set K,,for 1 <j≤m,which characterize a pattern prefix,and its partition are introduced,their some properties are discussed.Then,functions / and next are defined,the structure of K_j is described by f,a iterative computing method of / 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 / and the relationship between functions next and f,and its complexity is analyzed.更多还原