C# · 12月 19, 2021

数据结构与算法 (八) 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<m)使得t[k]=p[k],此时可以将P右移一个字符,重新进行比较

    2)KMP 匹配算法

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

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

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

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

2.算法实现