简单介绍
KMP——快速模式匹配算法（字符串匹配算法）
主要用途：查找字符串，查找字符串"ab"(目标字符串)在字符串"abc"(待查找字符串)中出现的位置。
即查找字符串"abc"是否包含字符串"ab"，如果包含，返回包含的起始位置
功能图示
比如计算str中是否含有ptr，算法由两部分组成：
1、计算
ptr每一位及之前的字符串中，前缀 和 后缀 公共部分的最大长度的next数组2、匹配
ptr和str，当ptr失配时，利用next数组，实现ptr的最大后移，从而避免不必要的匹配，减少匹配次数
前后缀
理解思路——关于next数组
-
定义：next数组是ptr每一位及之前的字符串中，前缀和后缀公共部分的最大长度的集合
-
计算：上图中
ABCD的前缀可能为：A,AB,ABC(除去最后一位）
后缀可能为：D,CD,BCD(除去第一位） 前后缀都没有重合，所以next[3]=0 -
对每一位及之前的字符串都要计算next数组的原因：因为两个字符串匹配的情况有很多种，可能是
ABC，可能是ABCD，也可能是ABCDE，所以要遍历一遍字符串来计算 -
作用：检查看后缀与前缀中有没有重合（红框部分），然后就能将ptr中的前缀（
第一个红框）位置直接移到重叠的后缀（第二个红框）的位置
next数组作用示意图
步骤解释
str: ABCDABEFGABCDABM
ptr: ABCDABM
(划线表示str和ptr中完全匹配的部分）
- 计算next数组，详情可见图解KMP算法
next数组值 - 开始匹配：
对于str和ptr两个字符串中，能匹配上则i++，j++；
直到匹配到E和M，发现不合适
不匹配图示 - 采用已匹配部分的字符串（即
ABCDAB）的next数组值（next[5]=2)，则ptr向前位移数为6-2=4（移动位数 = 已匹配的字符数 - 对应的部分匹配值），即i不动，j=next[j-1]
- 继续匹配，直到匹配成功，返回
i-j+1
