https://blog.csdn.net/qq_33375598/article/details/104479391 @[toc] 1 next数组 1.1 概念 假设有一个字符串s(下标从0开始),那么它以i号位结尾的子串就是s[0...i]。对于该子串来说,长度为k+1的前缀和和后缀和分别为s[0...k]和s[i-k...i]。 现定一个一个int型数组next, next[i]表示:使子串s[0...i]的前缀和s[0...k]等于后缀和[i-k...i]的最大k(==前缀和和后缀和可以重叠,但不能是s[0...i]本身==);如果找不到相等的前后缀和,那么就令next[i] = ...