KMP算法的理论研究

作者：韩光辉; 曾诚

来源：微电子学与计算机, 2013, (04): 30-33.

DOI：10.19304/j.cnki.issn1000-7180.2013.04.007

• 串匹配
• KMP算法
• 特征集
• 最大值函数
• 复杂度分析 string matching
• KMP algorithm
• characteristic set
• maximum value function
• complexity analysis

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

• 单位
  软件工程国家重点实验室; 武汉大学; 湖北大学