如何实现图解KMP字符串匹配算法的代码？

本文共计1824个文字，预计阅读时间需要8分钟。

KMP算法是最常见的字符串匹配算法，本文将通过图解的方式讲解KMP算法的工作过程，然后实现一个简单情况下的KMP算法。KMP算法与之前讲解的BM算法有一定的相似性。

kmp算法是最常见的字符串匹配算法，本篇文章将通过图解的方式讲解kmp算法的工作过程，然后再实现一个简单情况下的kmp算法。

　　kmp算法跟之前讲的bm算法思想有一定的相似性。之前提到过，bm算法中有个好后缀的概念，而在kmp中有个好前缀的概念，什么是好前缀，我们先来看下面这个例子。

　　观察上面这个例子，已经匹配的abcde称为好前缀，a与之后的bcde都不匹配，所以没有必要再比一次，直接滑动到e之后即可。

　　那如果好前缀中有互相匹配的字符呢？

　　

　　观察上面这个例子，这个时候如果我们直接滑到好前缀之后，则会过度滑动，错失匹配子串。那我们如何根据好前缀来进行合理滑动？

　　其实就是看当前的好前缀的前缀和后缀是否有匹配的，找到最长匹配长度，直接滑动。鉴于不止一次找最长匹配长度，我们完全可以先初始化一个数组，保存在当前好前缀情况下，最长匹配长度是多少，这时候我们的next数组就出来了。

　　我们定义一个next数组，表示在当前好前缀下，好前缀的前缀和后缀的最长匹配子串长度，这个最长匹配长度表示这个子串之前已经匹配过匹配了，不需要再次进行匹配，直接从子串的下一个字符开始匹配。

　　

　　我们是否每次算next[i]时都需要每一个字符进行匹配，是否可以根据next[i - 1]进行推导以便减少不必要的比较。