何为KMP？
我们先考虑一个字符串匹配的问题
暴力求解
一个简单地方法是，在主串枚举每一个字符，与模式串一位一位的匹配，失配则从主串的下一个字符开始，与模式串的第一位匹配。
这样匹配时间复杂度显然是不过关的。
KMP 算法
暴力算法之所以低效，因为它对主串中每个字符进行了大量的重复的比较，而 KMP 算法可以很好地解决这个问题。
这里先引入一个概念：border
border是字符串的最长公共前后缀，在KMP算法中用于优化字符串匹配效率，通过预处理border信息可跳过无效匹配位置
例如 ababa 这个字符串，他的前缀是 a，ab，aba，abab。后缀是 a，ba，aba，baba。故该字符串的 border 为 aba。
注意，前缀和后缀的长度都不能和字符串等长，故 border 的长度也不能和字符串等长。
再引入一个概念：Next 表
\(Next\) 表是一个存储 border 的表，其中 \(Next_i\) 表示以 \(S_i\) 结尾的前缀的 border。
如何求border?
要想做到合理的时间复杂度，border必须要在 \(O(n)\) 的时间复杂度下求出来，否则 KMP 就会退化。
若前缀往后一位与前缀 border 往后一位不相同，则往前找 border 的 border，直到出现相同的，设这个值为 \(j\)
如果 \(S_i = S_j\)，则 \(Next_{i + 1} = j + 1\)
否则 \(next_{i + 1} = 0\)。
例题：P3375 【模板】KMP