数据结构与算法 (八) KMP算法

概述本文章向大家介绍数据结构与算法 (八) KMP算法，主要包括数据结构与算法 (八) KMP算法使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

1.概念引导

       

       模式匹配：假设P是给定的子串，T是待查找的字符串，要求从T中找到与P相同的所有子串，这个问题称为模式匹配问题，P称为模式，T称为目标，如果T中存在一个或多个模式为P的子串，就给出该子串在T中的位置，称为匹配成功，否则，称为匹配失败

 2.算法原理      

    1).朴素的模式匹配（暴力匹配算法）

         用P中的字符依次与T中的字符串进行比较，首先从T的最左端开始比较，如果对于所有的k=0，1，3，...m-1,均有t[k]=p[k]，则匹配成功，否则，必有某个K（0≤k

    2)KMP 匹配算法

       从由于朴素的模式匹配算法，可以看出，每当本次匹配不成功时，P右移动一个字符，下一趟的比较有总是从P的第0个字符开始，而不管上一趟比较的中间结果是什么，因而回溯是不可避免的，而实际上这种回溯往往是不必要的，从而我们引出KMP匹配算法。

    KMP匹配算法是由knuth Morris 和Pratt提出的一种快速模式匹配算法：该算法解决了两个问题

    ①当比较出现不等时，确定下一趟比较前应该将P右移多少个字符

    ②P右移后应该从P中的那个字符开始和T中刚才比较时不等的那个字符继续比较

2.算法实现

总结

以上是内存溢出为你收集整理的数据结构与算法 (八) KMP算法全部内容，希望文章能够帮你解决数据结构与算法 (八) KMP算法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。