bm算法中函数shift的研究

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