串很有意思，就是我们认知的 String
1.蛮力算法，就是子串一个一个字符对比。
2.KMP 算法
时间复杂度 O(m+n)
关键问题在于构造，Next数组。但是，理解到 KMP 算法的前后缀重叠，还是比较快的。
基本思想是，如果目前的字母不匹配，我往前挪动几个字母，可以匹配到一致的？然后把这个距离记下来，每次在某个字母失配的时候，直接挑掉固定的位置。这就是 KMP 算法省时间的方法。
通俗理解：第一个遇到的字母记为0，之后再遇到的话，直接+1，例如
abcaaaabc
next = 000123412
（1）
（2）
（3）
王道单科书
Page 281
1.已知串 S = ‘aaab’ 写出 next 数组
next = 0123
2.已知串 S = ‘ababaaababaa’，写出 next 数组
next = 011234223456
解析：
ababaa ababaa
next = 011234 223456
原则一，失配时候，移动到子串的前一个；
原则二，算法永远找到子串最接近的。算法跑的时候，是按照子串重叠的字母数来计算的。
第二个字母 b 失配，子串移动到 1 位置，即第一个 a 位置。
第5个 a 失配，移动到 3 号位置，即和第三个 a 对比；第 6 个 a 失配，移动到 4 号位置。因为紧跟着 a ，向前移动到之前【含有 ‘a?’ 的子串】。
3.串 S = ‘ababaaababaa’，next 数组
next = -1, 00123 112345
4.串 S=‘aabaabaabaac’, P='aabaac'
next = -1,01012 345678
next = -1,01012
关注 ShoelessCai.com ，值得您的关注！
标签：子串,字母,next,算法,KMP,数据结构,失配 From： https://www.cnblogs.com/shoelesscai/p/18019591