KMP 算法
概述
在计算机科学中，Knuth-Morris-Pratt 字符串查找算法（简称：KMP 算法）
KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位
问题，说简单点就是我们平时常说的关键字搜索。模式串P就是关键字，如果它
在一个主串T中出现，就返回它的具体位置，否则返回-1（常用手段）。
该算法通过对这个词在不匹配时本身包含的信息来确定下一个匹配将在哪里开
始的发现，从而避免重新检查先前匹配的字符,提高程序运行效率。
具体来说，KMP 算法在匹配前会预处理模式串 P，得到一个 fail数组。借助
fail数组，可以在匹配过程中减少很多冗余的匹配操作，由此提高了算法的效率。
KMP 算法的时间复杂度为 O(n+m)(n,m分别是主串、模式串长度）。
评论0