如何理解KMT字符串匹配算法？如何计算出KMT数组？

来源：CSDN 时间：2023-03-02 09:43:44

KMT字符串匹配算法的核心是1. 如何计算出NEXT数组 2. 对该算法思想的理解。今天又复习了下这个算法，领悟了一套自认为更形象的理解。概括一句话就是：可以把KMT看成是暴力算法的加速版本或者跳跃版本，而如何加速跳跃则是NEXT数组的用途所在。

【资料图】

首先考虑暴力算法，T(目标串），P是模式串，即寻找P在T中的位置。

T: AACAAXEE

P: AACAAZDD

在X与Z处，出现了不匹配。按照暴力算法，我们会把P按步长1逐步的从T往后移，也就是第二次从T的B位置，第三次是C位置开始，以此类推。

KMT算法相比上面方法的改进之处就是，这个步长不用一直为1. 比如XZ不匹配的时候，可以直接步长3来进行第二步的匹配。也就是说P在当前不匹配的位置左边，即

T: AACAA

P:AACAA 寻找这两个最大的重叠部分（没移动前当然是最大的，但是这个时候已经发现XZ不匹配，所以我们要排除这个。可以把T跟P看出写着AACAA的并列的两张纸条，P往右慢慢移动，寻找最大的两张纸条重叠部分即可。）这样可以避免无意义的一步步的走，比如要是只走一步，

AACAA

AACAA，如果我们已经知道这个不是最大重叠串，那么也就是说这一步走完后，T跟P肯定不等（因为目前重叠的部分已经不等了），所以我们要寻找最大重叠串。

T：AACAAXEE

P： AACAAZDD

以T为参照就是T的当前下标不变，P移动到合适的下标位置。紧接着，发现XC不等，于是在C左边寻找最大的跳跃步长。

责任编辑：

标签：