在朴素的字符串模式匹配算法上，当遇到主串和模式串的字符不能匹配成功时，不论已经匹配了多少字符都要进行指针回溯，再开始下一轮的匹配。

这样效率是十分的低下的。ＫＭＰ算法，是在朴素的模式匹配算法的基础上，实现了匹配不成功时，不对主串指针进行回溯，使模式匹配的时间复杂度

降低为：O(n + m)。

对KMP算法的理解，在网上查找了不少资料，也看了算法导论上的描述，一直是一知半解。有次闲暇之余，想像着将模式串、主串都看着是条直线，进行了下推导，才恍然大悟。

KMP算法的核心思想是，在s[i] 和 p[j]不匹配时，不对主串进行指针回溯，而是在模式串中p中寻找k，用s[i] 和 p[k]进行下一轮的匹配。

可以用模式 P 与其自身进行比较，以预先计算出这些必要的信息。例如上图（c）中所示，由于 T[s’+1..s’+k] 是文本中已经知道的部分，所以它是字符串 P_q 的一个后缀。

朴素的字符串匹配算法又称为暴力匹配算法（Brute Force Algorithm），它的主要特点是：

1. 没有预处理阶段；
2. 滑动窗口总是后移 1 位；
3. 对模式中的字符的比较顺序不限定，可以从前到后，也可以从后到前；
4. 匹配阶段需要 O((n - m + 1)m) 的时间复杂度；
5. 需要 2n 次的字符比较；

Boyer-Moore 算法的主要特点有：

1. 对模式字符的比较顺序时从右向左；
2. 预处理需要 O(m + σ) 的时间和空间复杂度；
3. 匹配阶段需要 O(m × n) 的时间复杂度；
4. 匹配阶段在最坏情况下需要 3n 次字符比较；
5. 最优复杂度 O(n/m)；