更好地理解KMP算法

LeK2024-11-102024-11-10

如何更好地理解KMP算法

本文阅读前提：阅读下面这个链接的文章，对KMP有一定了解但不是很能理解的读者。

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solutions/732461/dai-ma-sui-xiang-lu-kmpsuan-fa-xiang-jie-mfbs

我们以代码随想录中的例子原字符串“aabaabaaf”和匹配串“aabaaf”为例，i为原字符串中的指针，j为匹配串中的指针。

当i=j=5时，此时i指向‘b’，j指向‘f’，两者不匹配，我们希望使用某个前缀子串来替代某个后缀子串，我们先从人类的直观角度来看，此时很明显要用匹配串的“aab”前缀子串来替代“aaf”的后缀子串，替代完成后i=5而j=2，此时继续进行匹配，i会一直增加而不会减小。

我们可以把j已走过的匹配字符串分为四部分：前缀、中间字符、后缀、当前字符，此时我们希望的是，当前字符不匹配时，可以让前缀+中间字符替换后缀+当前字符，能够替换的要求是：前缀与后缀相等，j指向中间字符，让这个中间字符与i指向的字符进行比较。所以我们的任务就是，怎么找出字符串中相等的前缀与后缀的最大长度，也即求next数组。为什么可以这样跳转，是因为后缀已经是匹配过的——后缀是和原字符串的一部分相等，既然后缀与原字符串相等，那么与后缀相同的前缀必然也是相等的，因此我们可以拿前缀替换这个后缀，将匹配串的指针向前移动。

如果能理解上一段的话，我们就能很好地理解KMP算法了。当匹配串[0:j]出现不匹配时，我们需要使用之前用过的匹配串，即[0:j-1]中的最长前缀的下一个中间字符，以我们刚刚的例子来说，[0:1]是与[3:4]匹配的前后缀，中间字符就是[2:2]中的第一个字符即‘b’，我们将匹配串的指针跳转到这个字符，我们就减少了[0:1]的重新比较和原字符串的指针的回退。

同时，利用分治的思想，我们跳转之后的字符串[0:2]仍然可以使用最长相等前后缀的做法，将[0:1]的前后缀进行替换。