图解KMP（有图有真相）

    对于任意一字符串p，我们总可以找到这么一个性质：以abcab为例，存在一相同的前缀与后缀ab，我们进一步假设abcab后面紧跟一字符d，也就是abcabd，而且在以它为模式串的匹配的过程d发生不匹配e，这时候就可以利用该前缀了：

abcabeabd

abcabd

由于已近匹配到e这个位置了，所以e前面的若干个字符串必然与d前面若干个字符串相同，至少ab这两个没问题，那么接下来我们就可以直接把e跟c来比较，而不是从头开始，这样就省下时间了

    上面这段推论是支撑KMP跳跃式比较字符串的的基石:前缀长度越短跳跃得越多，比较也就更快。

    其实对于任意长度为n的字符串p，我们都可以为它每一个字符都找到这个前缀，设其长度减一构成一个数组next[n]，如果next[k]=-1，那就是最好情况：该前缀长度为0,模式串可以跳跃得最远

    为了演示这种加速，直接上图

其中目标串t：annbcdanacadsannannacanna

模式串p：annacanna（next数组为{-1,-1,-1,0,-1,0,1,2,3}）

紫色的a就是我们所说的前缀，黄色是加速过程，也就是跳过比较的地方

红色的是发生了不匹配事件，绿色代表匹配

• 先解释加速过程123,123本来是朴素算法的步骤，这里被跳过了：由于next[2]=-1，所以p[3]发生不匹配时模式串可以跳的最远，直接把t[4]跟p[0]来比较，进入4

• 过程456由于在p[0]时就不匹配了，没有用到KMP的性质，而是走的朴素算法

• 78与123是同理

• 9,10与456同理

• 11与123同理

• 12,13与456同理

• 14,15与123不同理！，因为next[3]==0,可以从p[0]（所谓前缀）后面那一个字符n位置开始跟发生不匹配的t[17]比较

根据上图可以得出KMP算法的两大步：

1. 第一步求出属于模式串的next[n]数组

2. 第二步利用这个数组来跳跃式比较

代码见