浅论《数据结构》中KMP模式匹配算法讲解  

作　　者：杨凌雪 田宏兵 

机构地区：[1]六盘水师范学院数学与信息工程学院

出　　处：《科技资讯》2019年第19期196-197,200,共3页Science & Technology Information

摘　　要：模式匹配是《数据结构》中关于字符串的一个基本运算,一般有两种方法,分别为"朴素算法"与"KMP算法"。KMP算法是一种高效的字符匹配算法,它的关键在于当字符匹配失败以后,利用next数组中的信息使指针不需要回退,这样就减少了匹配的次数,提高效率。KMP算法不容易理解,该文通过举例等方法分析KMP算法的匹配原理及过程。Pattern matching is a basic operation on strings in Data Structure.There are generally two methods,namely"simple algorithm"and"KMP algorithm".The KMP algorithm is an efficient character matching algorithm.The key is that the information in the next array is used to make the pointer don’t need to be rolled back when the character matching fails,thus reducing the number of matching and improving efficiency.The KMP algorithm is not easy to understand.This paper analyzes the matching principle and process of KMP algorithm by examples.

关 键 词：模式匹配 next数组 KMP算法讲解 

分 类 号：TP311.12-4[自动化与计算机技术—计算机软件与理论]