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

【Abstract】 For the research and improvement of Boyer-Moore(BM) algorithm and its variants,it is very necessary to establish strict formal theory of the function shift in Boyer-Moore’s and its construction algorithm.A clear formal definition of shift was given.Then,characteristic sets of the pattern suffixes and its minimum value function were introduced,and the construction of shift was described by the characteristic sets,thus theoretical basis of shift and its construction algorithm were strictly established.Finally,a new construction algorithm of shift was presented based on the construction theorem of shift and iterative computing method of the minimum value function.It is proved that the algorithm has linear time and space complexity.The theoretical analysis and computing results show that the algorithm is simpler,and its complexity of computation is lower,so it is more suitable for hardware implementation compared with several existing algorithms.更多还原