KMP算法，不管是主算法还是预处理的next求取，在学习中要深刻把握住两个不同的下标，思考何时应该往回退（术语回溯），何时应该+1，何时应该置零。
有主串s，模式串p。求：s有多少子串等于p？出现在s的什么位置？ 详细描述见洛谷P3375 【模板】KMP字符串匹配
本文略去暴力算法的分析。
记p的前i位为子串t。 若存在u，使得u既是t的前缀，也是t的后缀，则u最长的长度记录于next[i]。
其实我感觉这里命名为next怪怪的，但是我也没有想到更贴切且简洁的描述的方式，这样看来，就按它的用途来命名也无可厚非。
匹配进行到主串的pos1位和模式串的第pos2位时，发现不匹配（在这之前的pos2-1位全部匹配）。在这时如果把pos2退回到第一位，就是暴力算法；而退回到已经和s匹配了的后一项，则为KMP算法。
如何回退呢？这里就要用到的就是next数组，它可以指引我们应该回退到第几位。 图转自 洛谷网校 阮行止
值得注意的是，如果pos2已经退回到0了，那就无法继续回退了，此时应该将pos1加1进行下一步的比较。
接下来描述如何求取next。 next数组的思路和动规更加贴近，若已知前i-1位的next数组，如何求取第i位的next呢？
记录next[i-1]为tmp。
如果p[i]=p[tmp+1]，那么next[i]就等于tmp+1如果p[i]!=p[tmp+1]，那么就回溯tmp，令tmp=next[tmp]