KMP算法中next数组的计算方法研究

• 作者: 汤亚玲
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: KMP next数组 递推 递归
• 年，卷（期）: 2009,（6）
• 所属期刊栏目: 智能、算法、系统工程
• 页码范围: 98-101
• 页数: 4页
• 分类号: TP301.6
• 字数: 4423字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-629X.2009.06.027

摘要

next数组的计算方法是KMP(Knuth-Morris-Pratt)算法的难点和核心.当前数据结构教材中普遍采用递推的方式来计算next数组值.文中给出一种新的采用递归思想设计的计算next数组的算法;并对当前数据结构教材中对next数组定义的其它一些改进方式进行了讨论与分析.实验数据表明,递归算法的思想正确;并且,从算法设计上考虑,采用递归方法设计的算法具有思路清晰、易于理解和分析的优点.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	汤亚玲	安徽工业大学计算机学院	25	120	6.0	10.0