文献类型：期刊文章

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

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

出　　处：《微电子学与计算机》

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

年　　份：2013

卷　　号：30

期　　号：4

起止页码：30-33

语　　种：中文

收录情况：BDHX、BDHX2011、CSCD、CSCD_E2013_2014、JST、ZGKJHX、核心刊

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

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

分 类 号：TP301.6]