STRFFT 的意思是不是 街首

快速卷积匹配就不说了，之前训卷积的时候做过很多个这样的题目，套路就是 sigma 条件转艾弗森括号后进行和、差卷积匹配，或者对哈希值进行匹配。可以参考 P4173 和 qoj11617 等。

那么我就讲一下周期相关的事情。现在题解区里大家对“哪些长度是周期”的认知还是“先去掉一定不可能的，再推理矛盾的”，这里给出一个通用的结论。

需要注意当周期被规定为满周期的时候显然还要加个条件就是 $d\mid |s|$。接下来证明上面给出的结论。

充分性： 即若条件不成立一定有周期。考虑对于所有 $0\le r<d$，根据不存在 $kd=j-i=(k_2d+r)-(k_1d+r)$，一定有 $s_r\sim s_{r+d}\sim \dots\sim s_{r+md}$（其中 $x\sim y$ 表示他们要么相等要么有通配符在里面，如上文所述）。因此满足周期性质。

必要性： 若条件成立，设 $d\mid (j-i)=T$，且 $T$ 是最小的满足这个条件的数。那么归纳。若 $d=T$ 显然 $d$ 不是周期；否则一定有 $s_{i}\ne s_{i+d}$ 或 $s_{i+d}\ne s_j$，故 $T$ 非最小，矛盾。

因此得证。我们只需要卷积出所有 $j-i$ 之后标记它们所有因数即可。使用枚举倍数被动获得 tag 的方法，可以做到和 NTT 一样的复杂度，因此本题复杂度 $\Theta(n\log n)$。

反思： 一个很有意思的点在于其他题解一直声称本题“问号不是通配”，这只是对周期的性质不了解。当串完好的时候，若 $s_i\ne s_{i+2d}$，那么一定有 $s_i\ne s_{i+d}$ 或 $s_{i+d}\ne s_{i+2d}$，因此只将所有的 $(j-i)$ ban 掉也是能够通过；但是像这个题，就需要深入挖掘周期的性质，ban 掉所有 $d\mid (j-i)$。这样子就不用被通配符迷惑了。

NOIP 2025 RP++