一般来说在你没学过KMP算法前，你解决字符串匹配问题会采用BF算法——BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

虽然这种方法可行，但是时间复杂度为O(m*n),对于长字符串效率较低，所以有人就研究出了KMP算法来提高解决该类问题时的效率问题。

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特--莫里斯--普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

在讲KMP算法前我们先引入前后缀概念

1.前缀及一个字符串的第一个字母到倒数第二个字母

2.后缀及一个字符串的最后一个字母到正数第二个字母

举个例子 对于字符串 abaabb

前缀：abaab        后缀：baabb

3.最长相等的前后缀

对于 a既没有前缀也没有后缀所以它最长相等的前后缀长度为2

对于abaab最长相等的前后缀是ab，长度为2

对于ababa最长相等的前后缀是aba，长度是3

核心思想

本章讲了KMP算法的理论实现，关于KMP算法的代码实现以及next数组的优化放到下一章来进行赘述。