。常规的字符串匹配我们一般都这样做，使用两个指针，一个指向主串，一个指向模式串，如果他俩指向的字符一样，他俩同时往右移一步，如果他俩指向的字符不一样，模式串的指针重新指向他的第一个字符，主串的指针指向他上次开始匹配的下一个字符，如下图所示。

　　我们看到当模式串和主串匹配失败的时候，模式串会从头开始重新匹配，主串也会回退，但我们知道失败字符之前的子串都是匹配成功的，那么这个信息能不能被我们利用呢？当然可以，这个就是我们这里要讲的KMP算法，他就是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

　　当使用KMP算法的时候，如果某个字符匹配失败，主串指针不回退，而模式串指针不一定回到他的第一个字符，如下图所示。

　　当字符e和d匹配失败之后，主串指针不回退，模式串指针指向字符c，然后在继续判断。主串指针不回退好操作，但模式串指针怎么确定是回到字符c，而不是其他位置呢？这是因为在字符e匹配失败后，字符e前面有2个字符ab和最开始的2个字符ab相同，所以我们可以跳过前2个字符。也就是说模式串匹配某一个字符失败的时候，如果这个失败的字符前面有m个字符和最开始的m个字符相同，那么下次比较的时候就可以跳过模式串的前m个字符，如下图所示。

　　通过上面的图我们可以知道，当某个字符匹配失败的时候，他前面的肯定都是成功的，也就是说字符串s1和字符串s2完全一样。在模式串中，匹配失败的字符前面b4和b3是相同的，所以我们可以得到b1，b2，b3，b4都是相同的，也就是说b2和b3也是相同的，既然是相同的，跳过即可，不需要在比较了，直接从他们的下一个字符开始匹配。

　　KMP算法的核心部分就是找出模式串中每个字符前面到底有多少字符和最开始的字符相同，我们用next数组表示。有的描述成真前缀和真后缀的相同的数量。这里要注意当前字符前面的字符不包含第1个字符，最开始的字符也不能包含当前字符，比如在模式串abc中不能说字符c前面有ab和最开始的ab相同，来看下表。

　　我们看到字符e前面有ab和最开始的字符ab相同，长度是2。在看第2个a前面没有（不包含自己）和最开始字符有相同的，所以是0。在任何模式串的第2个字符前面都没有和最开始字符有相同的，因为前面的是不包含第一个字符，所以next[1]=0。如果第2个没有，那么第1个就更没有了，为了区分，可以让next[0]=-1，当然等于0也可以，需要特殊处理下即可。我们先来看下next数组怎么求。

　　使用两个指针i和j，其中j是字符p[i]前面与最开始字符相同的数量，也是next[i]。如果p[j]==p[i]，也就是说字符p[i+1]前面有j+1个字符和最开始的j+1个字符相同，所以可以得到next[i+1]=j+1，这个很容易理解。如果p[j]！=p[i]，我们让指针j等于next[j]，然后重新和p[i]比较，这就是回退，这个回退也是KMP算法的最核心部分，我们来分析下为什么要这样回退。

　　如上图所示，如果nxet[j]大于0，那么j前面的b2和b1是相同的，我们知道S1和S2也是相同的，所以我们可以得出b1，b2，b3，b4都是相同的，如果p[i]!=p[j]，只需要让j回退到next[j]，然后i和j在重新比较，这个next[j]就是b1的长度，因为b1和b4是相同的，所以不需要再比较了。如果还不相同，j继续回退，直到回退到-1为止，我们拿个真实的字符串看下，如下图所示。

　　我们看到b1，b2，b3，b4是相同的，他们都是字符串abc，如果p[i]!=p[j]，我们就让j回退到next[j]，因为他们前面b1和b4是相同的，没必须要在比较了，最后再来看下代码。

　　我们来看下表 ，当模式串在下标为4的位置匹配失败的时候，下一步j会回退到下标为1的位置，但这两个位置的字符是一样的，既然一样，拿过来比较也是不会成功，所以如果字符一样，我们可以优化一下，往前查找相同的子串。

　　如果前面查找的还是相同的，我们该怎么办呢？是不是需要写个递归，继续往前找？实际上是不需要的，比如模式串aaaaaaaaaab，如果没优化他是这样的。

　　如果优化之后，当最后一个a匹配不成功的时候，他会回退到前面一个a，实际上前一个a在计算的时候已经回退过了，就是-1，所以不需要递归，直接赋值就行。