考前记忆模板。

我们回忆一下 $next$ 数组的含义:

$next[i]$ 表示在 $[1,i-1]$ 内,前缀与后缀相同的部分最长是多长。可以理解为,若第 $i$ 位失配了,至少要往前跳多少步,才可能重新匹配得上。

于是对于匹配串,预处理出它的 $next$ 数组,然后对文本串逐位匹配即可。

后记 不知道为什么我内心一直觉得 NOIp 会考这个算法。。。说不定被我奶中了呢。。。