数据结构与算法 (八) 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.算法实现

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!