上午学习了kmp算法的思想，下午学习了如何实现kmp算法，并对这些内容进行了总结。
写在前面
文章中可能会先讲解很多貌似毫不相关的知识点，但这些都是学习kmp算法需要知道的东西，先了解这些知识点后我们就可以更好的理解kmp算法了。
目录
kmp的作用
在一个已知字符串（文本串）中查找子串（模式串）的位置,也叫做串的模式匹配。
暴力算法简介
从主串s 和子串t 的第一个字符开始，将两字符串的字符一一比对，如果出现某个字符不匹配，主串回溯到第二个字符，子串回溯到第一个字符再进行一一比对......一直到子串字符全部匹配成功。
最好的时间复杂度：O(n)
最坏的时间复杂度：O(m*n)
kmp算法相对于暴力算法的优化
KMP 算法主要是通过消除主串指针的回溯，以及改变字串回溯的位置来提高匹配的效率的
具体实现就是通过一个next()函数（即构造的前缀表）实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)
前后缀
前缀表示包含第一个字符，但不包含最后一个字符的字串
后缀表示包含最后一个字符，但不包含第一个字符的字串
上例子：
字符串 abcdab
前缀的集合：{a,ab,abc,abcd,abcda}
后缀的集合：{b,ab,dab,cdab,bcdab}
最长相等前后缀
字符串 abcdab
前缀的集合：{a,ab,abc,abcd,abcda}
后缀的集合：{b,ab,dab,cdab,bcdab}
最长相等前后缀就是ab
理解了这里，关于kmp算法子串回溯到哪个字符，现在可以着手解决了
获取前缀值
事实上，每一个字符前的字符串都有最长相等前后缀，而且最长相等前后缀的长度是我们移位的关键，所以我们单独用一个next数组存储子串的最长相等前后缀的长度。
next数组即我们需要构造的前缀表
每一个字符前的字符串的最长相等前后缀即该字符的前缀值
前缀值：
前缀值不仅仅代表着对应位置字符串前后缀相同元素长度的最大值
因为是前后缀的公共元素，它还可以表示该位置与从字符串首位起固定位置的字符相同，即指向自身与其相同的元素的位置。
文本串用例：ABABD
前缀表（前缀值表）
对于任意一个字符串，我们很容易得到它的第一个前缀字符（数组索引为0）对应的前缀值一定为0（因为第一个前缀字符只有一个字符A没有前后缀，所以也不存在公共元素）
构建前缀表
分为三步：
1、初始化
2、前后缀的末尾不相同时怎么处理（有的文章直接就写个前后缀，让你看的一头雾水）
3、前后缀的末尾相同时怎么处理
void kmp(next,s)
{
j=0;
next[0]=0;//初始化
for(i=0;i<s.size();i++)
{
while(i>0&&s[i]!=s[j])
j=next[i-1];//前后缀的末尾不相同时怎么处理
if(s[i]==s[j]) j++;//前后缀的末尾相同时怎么处理
next[i]=j;//更新
}
}