设匹配函数 \(C(x,y)\) 为字符 \(x\) 和字符 \(y\) 匹配的值，是我们自己定义的值。
两个字符串匹配的值就是对应位置上的字符匹配的值的和。
对于文本串 \(S\) 和模式串 \(T\)，现在要求出 \(T\) 在 \(S\) 中所有匹配的位置。
为了化成卷积的形式，把 \(T\) 反转。
这样 \(T\) 和 \(S\) 以 \(i\) 为结尾的子串的匹配值为：
\[\sum_{j=0}^{|T|-1}C(S_{i-j},T_j) \]为了能够区分不同位置的匹配值，定义生成函数：\(P(x)\)，\([x^i]\) 代表 \(T\) 与 \(S\) 以 \(i\) 结尾的子串的匹配值。
那么：
\[P(x)=\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}C(S_{i-j},T_j) \]为了能通过观察匹配值来确定两个字符串，构造匹配函数 \(C(x,y)=(x-y)^2\)（字符的权值需满足两两不同，可以使用 ASCII 码来作为权值），则两个字符串匹配当且仅当匹配值为 \(0\)．
那么：
\[\begin{aligned} P(x)&=\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}(S_{i-j}-T_j)^2 \\ &=\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}{S_{i-j}}^2+{T_j}^2+S_{i-j}T_j \\ &=\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}{S_{i-j}}^2+\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}{T_j}^2+\sum_{i=|T|-1}^{|S|}\sum_{j=0}^{|T|-1}S_{i-j}x^{i-j}T_jx^j \end{aligned} \]另外，为了使得边界满足卷积的形式，对于"溢出"的部分定义其权值为 \(0\)，也就是我们需要计算：
\[\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}{S_{i-j}}^2+\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}{T_j}^2+\sum_{i=|T|-1}^{|S|}\sum_{j=0}^{i}S_{i-j}x^{i-j}T_jx^j \]前两个柿子可以预处理前缀和来做到线性求出，后面是个卷积的形式，可以通过 FFT \(\mathcal{O}(n\log n)\) 求出。
所以就可以 \(\mathcal{O}(n\log n)\) 做到字符串匹配了。
栗题一 luoguP4173
带通配符的字符串匹配。
尝试构造匹配函数 \(C(x,y)\) 满足：
-
\(x\) 或 \(y\) 为通配符时值为 \(0\)；
-
\(x\) 和 \(y\) 都不为通配符，且相同时值为 \(0\)；
-
\(x\) 和 \(y\) 都不为通配符，且不相同时值 \(>0\)．
设通配符的权值为 \(0\)，\(C(x,y)=(x-y)^2xy\)．
\[\begin{aligned} P(x)&=\sum_{i=|T|-1}^{|S|}x^i\sum_{j=0}^{|T|-1}(S_{i-j}-T_j)^2S_{i-j}T_j \\ &=S^3*T-2S^2*T^2+S*T^3 \end{aligned} \]（这里的次方是点乘，\(*\) 为卷积）
三次卷积，时间复杂度 \(\mathcal{O}(n\log n)\)．
栗题二 Codeforces 528 D
分别仅考虑 \(A,C,G,T\)，把匹配成功的位置取个交集就可以。
现在仅考虑 \(A\)，把 \(S\) 中不会和 \(A\) 匹配上的位置上的字符设为 \(o\)，把 \(T\) 中不是 \(A\) 的字符设为 \(\#\)，则匹配函数 \(C(x,y)\) （其中 \(x\) 来自 \(S\)，\(y\) 来自 \(T\)）要满足：
- \(=0,x=A,y=A\)；
- \(=0,x=A,y=\#\)；
- \(>0,x=o,y=A\)；
- \(=0,x=o,y=\#\)．
这样的 \(C\) 才能满足匹配成功值为 \(0\)，否则大于 \(0\)．
设：
-
\(S\) 中的 \(A\) 值为 \(0\)，\(o\) 值为 \(1\)；
-
\(T\) 中的 \(A\) 值为 \(1\)，\(\#\) 值为 \(0\)；
-
\(C(x,y)=(x-y)^2\)．
用普通字符串匹配做。