数据结构与算法（4）KMP算法易懂版（看毛片算法，这下要是还看不懂你就来打我吧）
目录
KMP算法其实不难，只是市面上的千人千面的描述，把一个简单的算法越描述越乱了。
KMP由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）
比如在主串s=“ababcabcacbab”中找出模式串p="abcac"第一次出现的位置。
1、字符串的前缀、后缀、最长相等前后缀
前缀：除最后一个字符之外，字符串其余部分的所有头部子串
后缀：除第一个字符之外，字符串其余部分的所有尾部子串
‘a’的前缀和后缀都是空集，最长相等前缀和后缀长度为0。
“ab”的前缀为{a},后缀为{b}，{a}∩{b}=∅，最长相等前后缀长度为0
‘aba’的前缀为{a,ab},后缀为{a,ba}，{a}∩{b}={a}，最长相等前后缀长度为1
‘abab’的前缀为{a,ab,aba},后缀为{b,ab,bab}，{a}∩{b}={ab}，最长相等前后缀长度为2
2、部分匹配值（Partial Match，PM）
字符串“abcac”的部分匹配值为00010。
部分匹配值的每一位代表的含义就是当前最长相等前后缀长度。
3、暴力匹配
4、KMP算法
KMP算法的原理是对子串进行分析,找出已匹配部分的最大相同前后缀，尽可能减少暴力**中的频繁回溯问题。
移动位数：已匹配的字符数-对应的部分匹配值
KMP算法的优点在于父串不用回退，回退操作在子串上，对子串进行分析即可。