文献类型：期刊文章

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

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

出　　处：《计算机应用》

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

年　　份：2013

卷　　号：33

期　　号：8

起止页码：2379-2382

语　　种：中文

收录情况：AJ、BDHX、BDHX2011、CSA、CSA-PROQEUST、CSCD、CSCD2013_2014、IC、INSPEC、JST、RCCSE、ZGKJHX、ZMATH、核心刊

摘　　要：建立BM算法中函数shift及其构造算法的严格的形式理论,对于BM算法及其各种变形的研究与改进是十分必要的。给出了shift的一个清晰的形式定义,引入模式串后缀的特征集及其最小值函数,通过特征集描述了shift的构造,从而严格建立了shift及其构造算法的理论基础。根据shift的构造定理与最小值函数的迭代计算方法,给出了shift的一个新的构造算法,证明了该算法具有线性的时间与空间复杂度。理论分析和计算结果表明,该算法比已有算法更简单,计算复杂度更低,因而更适合硬件实现。

关 键 词：串匹配 BM算法 好后缀规则  shift函数  复杂度分析  

分 类 号：TP301.6]