KMP 算法（Knuth-Morris-Pratt 算法）是其中一个著名的、传统的字符串匹配算法，效率比较高。KMP算法由D.E.Knuth，J.H.Morris和V.R.Pratt在 Brute-Force算法的基础上提出的模式匹配的改进算法。因此人们称它为“克努特—莫里斯—普拉特算法”，简称KMP算法。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。Brute- Force算法在模式串中有多个字符和主串中的若干个连续字符比较都相等，但最后一个字符比较不相等时，主串的比较位置需要回退。KMP算法在上述情况下,主串位置不需要回退，从而可以大大提高效率。要点：实现方法主要是通过一个LPS（Longest Proper Suffix）数组实现，数组本身包含了模式串的局部匹配信息。KMP算法的时间复杂度为O(m+n) 。有些人以为讲清楚了，其实没有。学习算法，阅读文字浪费时间，看图及阅读代码最好。
