改进的模式匹配算法-软考在线

改进的模式匹配算法



考试要求：掌握

知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用数据结构 > 线性结构 > 串 > 串的模式匹配

改进的模式匹配算法又称为KMP算法（由D.E.Knuth、V.R.Pratt和J.H.Morris提出），其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串字符的位置指针，而是利用已经得到的“部分匹配”的结果，将模式串向后“滑动”尽可能远的距离，再继续进行比较。此算法可在O（n+m）的时间内完成。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5