女娲补天之KMP

$KMP$算法可在一个字符串$S$内查找另一个字符串$a$所有的出现位置。

这里待匹配的长字符串为$s$，短字符串为$a$
注意点：
1. 指向字符串$a$的指针$j$是从$0$开始的！
2. 字符串$a$自我匹配的时候注意从2开始
3. 字符串$a$自我匹配的时候需要计算每个点对应的ne[i]，所以每轮都要ne[i] = j，只有a[i] = a[j + 1]才会j += 1。
4. 因为while循环如果匹配失败，j = ne[j]，$j$会不断向前移动，所以判断条件是j > 0
5. 在正式匹配中，每次匹配成功后，需要先执行判断if s[i] == p[j + 1]:，然后再看$j$是否指向末尾j == n，二者的顺序不能改变!!!!!

延伸出的结论：
1. KMP算法得到的ne数组，n - ne[n]是长度为n的字符串的最小循环节
2. 所有循环节的长度都是最小循环节长度的整数倍
3. 注意这里的循环节并不能完整覆盖整个字符串的，最后几位可能只有循环节的前几个字母

刷题列表

好像只有模板题和背结论的hhh

AcWing 831. KMP字符串

只默几次真有点记不住hhh
3.23默写：在找到匹配的下标后忘记j = ne[j]
3.31默写：自我匹配构造ne[]数组时忘记要从2开始匹配

AcWing 141. 周期

这篇是题解