一文搞定KMP字符串匹配算法

我一直坚信一点，就是算法不分好和坏，只要能解决问题的算法都是好算法，有一句俗话，叫是骡子是马拉出去溜溜，算法也是一样的，你能解决问题，那这个算法就是好算法，算法的适用场景是不一样的，非常复杂的算法它在小型的设备上就会受到局限性，反而简单一些的算法会受到欢迎，今天呢，就跟大家聊聊KMP字符串匹配算法，很多新手看这个算法，比较蒙圈，我今天就将这个算法讲解透彻，有兴趣的同学可以看看，多多关注我，给我更大的动力。

现在给你一篇文章，在文章中，找到你想要的内容，这就是字符串匹配，那么这里就涉及到如何查找的问题，我们假设文章的内容为”abcdefgabcabc”，现在我们需要在这个串中，查找是否存在”abcabc”这个子串，对于很多人，都能想到一种算法，我们委婉的说一下，就是朴素的匹配算法，见下面的示意图，一目了然，请看下面：

1. 最直接的匹配算法（朴素的匹配算法）

1) 经过比较我们发现，主串S的第一到第三个字符和匹配串T的前三个字符对应上了，但是第四个字符没有和T的第四个字符匹配上，那么继续匹配。

2) 主串从第二个字符b开始，和T进行匹配，发现b和a不相等，继续下一轮的匹配。

3) 主串从第三个字符c开始与T进行匹配，发现c和a不相等，继续下一轮的匹配。

4)主串的第四个字符d开始和T进行匹配，发现d和a不相等，继续下一轮的匹配。

5）主串的第五个字符e和T进行匹配，发现e和a不相等，继续下一轮的匹配。

6）主串的第六个字符f和T进行匹配，发现f和a不相等，继续下一轮的匹配。

7）主串的第七个字符g和T进行匹配，发现g和a不匹配，继续下一轮的匹配。

8）主串的第八个字符直到末尾和T进行了全匹配，全部相等，匹配成功。

经过上面的匹配流程，我们知道了朴素的匹配算法的效率是比较低效的，每次和匹配串T匹配不上的时候，就从主串的下一个字符开始和T进行匹配，那么我们发现，匹配失败后，变的是主串的位置，匹配串T始终从首字符和主串进行匹配，这种效率极其低下，也就是出现了大量重复的匹配，最坏的情况是把主串全部遍历一遍，这个你能忍受的了吗？我是忍受不了。

所以，出现了KMP的匹配算法，KMP是对朴素算法的一种改进，其实思想非常简单，我来一一说明。

2. KMP匹配算法

有三位前辈，D.E.Knuth、J.H.Morris和 VR.Pratt共同研究，针对朴素匹配算法进行了改进，提出了KMP的匹配算法。

KMP算法就是针对大量重复匹配而提出的一种改进算法，避免了重复匹配的过程，那么下面我们来研究一下KMP是如何避免重复匹配的呢？

我们可以看到，主串S和子串T在匹配过程中，d字符和a字符没有匹配上，匹配上的是abc这三个字符，按照朴素算法，会用主串的第二个字符和子串T的开头进行匹配，但是你有没有发现，对于主串S来说，从第二个字符开始匹配的话，这种做法合理吗？是不是显得多余，因为匹配上的前三个字符abc各不相等，也就是说明了主串S的第二个字符和子串T的第一个字符a一定不相等，所以主串没有必要从第二个字符开始和T进行匹配，应该从第四个字符和T的首字符开始匹配，这就是KMP算法的核心思想，那么使用KMP算法后，匹配的示意图如下：

看到上面的示意图，可以看出KMP算法的思想，主串S直接跳过b和c，开始用d和子串T进行匹配，跳过了2个字节。

提高了一定的匹配效率。

上面是KMP算法处理的第一种情况，我们来看一下第二种情况，主串S为”abadef”，子串T为”abaf”，接下来我们看看匹配的过程：

由于主串S的前三个字符和子串T相等，那么现在我们就思考一下，这个时候，主串应该从第几个字符开始匹配，子串开始从第几个字符开始匹配呢？

我们观察到主串和子串开始匹配的串为“aba”，这个串有些特殊，就是这个串的前缀a和后缀a相等，那么对于这样的字符串，在没有匹配的情况下，子串T还是从第一个字符开始匹配吗？

当然不是，因为前缀和后缀相等，所以，子串T从前缀串的下一个字符开始和主串进行匹配即可，也就是从第二个字符b开始和主串的d开始匹配。

这样就少了一次移动，提高了一次效率，那么第二次匹配的过程如下：