引子
昨天比赛遇到一道用kmp算法的题目，结果连$next$数组是什么都忘了qwq，于是今天恶补了一下kmp算法，写一篇总结，希望能帮助到和我一样的蒟蒻，那我们开始吧。
本文主要是讲关于$next$数组，学习完整算法可以移步这里
参考资料：
字符串border原理小结&KMP优化 - lx_tyin - 博客园 (cnblogs.com)
基础next数组
概念讲解
首先引入一个概念$border$ ：字符串的子串既是它的前缀又是它的后缀，一般不包括本身。
图1
图2
ok，当我们理解了border的概念后，就可以引入$next$数组的概念啦，即当前字符串中最长的$border$的长度，同样也可以对应$$border$$后一个字符的下标（记一下等下构造会用到）。结合下面的例子熟悉一下吧。
如$next[i]$为字符串$s$中由$s_0$到$s_{i - 1}$组成的字符串的最长的$border$。比如，$s = ababab$，那么$next[3]$为字符串$abab$的最长的$border$的长度即为$2$。
图3
构造过程
构造$next$数组的过程和$kmp$本身很像，都是$O(n)$的时间复杂度算出答案，而且中间的步骤也基本相同。这个时候有些读者急了不是，一个是求模式串在文本串中出现的次数，一个是求当前字符串的最长的$border$ 的长度，怎么可能一样嘛，垃圾文章不看了😒
两者有很多相同之处，当然也有不同的地方，且听我慢慢分析，保教包会🥰
先上代码
//make next
nxt[0] = 0; //第一个字符没有border
for(ll i = 1, j = 0; i < pat.size(); i ++ ) {
while(j != 0 && pat[i] != pat[j]) j = nxt[j - 1];//回溯
//i每增加1，就只是往后一位字符，所以j也最多往后一位
if(pat[i] == pat[j]) j ++ ;
nxt[i] = j;
}省流：构造$next$数组就是将$border$看成模式串，原本的模式串看成文本串，通过动态规划的思想去完成构造（其实$kmp$也是动态规划）。
先创造一个自己的“影分身”$j$，它代表现在上一个字符串的$next$值，它同时又是上一个字符的$border$（前缀）的后一位字符的下标，这时候在上一个字符串结尾加入$pat_i$，比较$pat_i$（当前字符串的最后一位）与$pat_j$。
如果$pat_i = pat_j$，那当前字符串的$next$值就是上一个字符串的$next$加$1$。
举个例子，字符串$s = ababa$，当$i = 3$时，$border = ab$，$j = 2$。
那么当$i = 4$ 时，$pat_j = a$, $pat_i = a$，所以$border$就变成了$aba$，求出$nxt_4 = ++ j = 3$ 。
图4
如果$pat_i \not= pat_j$，我们知道$border$其实也是字符串的一部分而且我们已经求出了它的$border$，所以我们通过回溯去找当前$border$的$border$，然后比较$pat_i$与$pat_j$，直到找到一样的字符或者当前$border$没有$border$。（是不是和$kmp$一模一样！）
举个例子，字符串$s = ababac$，当$i = 4$时，$border = aba$，$j = 3$。
那么当$i = 5$ 时，$pat_j = b$, $pat_i = c$，$pat_i \not= pat_j$，所以我们要去回溯$border = aba$的$border$，而$ab$的$border$其实就是$nxt_2 = 1$，所以$border$更新为$a$，$pat_j$更新为$s_1 = b$，再去比较，发现还是不一样，再次回溯发现$a$没有$border$后，就终止循环。
图5
由上看出，构造$next$数组的过程和$kmp$都是每次往后比较一位，而且在后一位不同的时候需要去回溯。不同点就是构造$next$数组的过程中模式串一直在变化（即$border$不停在变化），而$kmp$中模式串则不变。
优化
其实在构造$next$数组的过程中有没有发现，在字符串$s = ababac$这个例子中，我们明明知道$c \not= b$，却还要去回溯，累不累啊，而且在之后的$kmp$中如果还要用到$nxt4$的话，结果肯定还是浪费力气，因为$s_1 = s_3 = b$，所以当$s3 \not= char$时，$s1 $肯定也不相等啊。
所以我们优化的过程就是判断$pat_{i + 1}$ 和$pat_{j + 1}$的大小，如果相等，就让$nxt_i = nxt_j$。
上代码！
//搬运自https://zhuanlan.zhihu.com/p/105629613
nxt[0] = 0;
for(ll i = 1, j = 0; i < pat.size(); i ++ ) {
while(j != 0 && pat[i] != pat[j]) j = nxt[j - 1];
bool b = pat[i] == pat[j], c = pat[i + 1] == pat[j + 1];
if(b) nxt[i] = nxt[j ++ ] ;
if(!b || !c) nxt[i] = j;
}小结
本蒟蒻第一次写这么深奥的文章，其实很多知识点也是边写边了解，像$border$和优化，有不当之处希望各位佬多多指出orz