==== 序列中两两之差 ==== [[https://codeforces.com/problemset/problem/1398/G|CF1398G]] 把题目化简之后，就是给一个序列 $a_i$ 要能高效地得到 $a_i - a_j$ 构成的集合。构造两个生成函数 $\sum x^{a_i}$ 和 $\sum x^{-a_i}$，那么这两个多项式相乘得到的答案 $f(x)$ 中如果 $x^i$ 的系数不为 $0$ 则 $i$ 可以被表示为序列中某两个数的差。


/*
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
*/
#include
#define ALL(x) (x).begin(),(x).end()
#define ll long long
#define db double
#define ull unsigned long long
#define pii_ pair
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<


\\

==== 字符串匹配 ====

先考虑如何用 $\text{FFT}$ 做和 $\text{KMP}$ 一样的事：

记 $s$ 串为长度为 $m$ 的模式串，$t$ 串为长度为 $n$ 的文本串，下标均从 $0$ 开始。目标是找出所有 $x$ 满足 $\forall i\in [0,m),t_{x-m+i+1} = s_i$。

上述条件可用一个式子来表示 $\sum _{i=0}^{m-1} (s_i - t_{x-m+i+1})^2 = 0$，展开后为 $\sum _{i=0}^{m-1} s_i^2 + t_{x-m+i+1}^2 - 2\cdot s_i\cdot t_{x-m+i+1}$。

两个平方项都可以通过前缀和得到。乘积项转换一下就会变成一个卷积的形式：把 $s$ 串翻转一下得到 $rs$ 串，于是乘积项就是 $\sum _{i=0}^{m-1} 2\cdot rs_{m-i-1} \cdot t_{x-m+i+1} = \sum _{i=0}^{m-1} 2\cdot rs_i \cdot t_{x-i}$。所以这里就可以用$\text{FFT}$处理的到。

最后的判断条件：卷积之后的多项式为 $f(x)$，在 $t$ 串的 $x$ 位置匹配当且仅当 $f(x) + pres[m-1] + pret[x] - pret[x-m-2] = 0$。总复杂度为 $O(nlogn)$。

虽然 $\text{FFT}$ 多了一个 $log$ 的复杂度，但有些匹配是 $\text{KMP}$ 无法做但是 $\text{FFT}$ 可以做。

[[https://www.luogu.com.cn/problem/P4173|P4173]]

在正常匹配的基础上扩大了字符集的范围，多了一种 $*$ 字符（可以匹配任何字符）。这样之后就不能用 $\text{KMP}$ 了，因为 $\text{KMP}$ 需要满足一种等价关系，而通配符 $*$ 的存在就不满足等价关系：$a = * 且 b = *$ 但没有传递性 $a = b$。

考虑用上述一样的方法来构造多项式函数 $\sum_{i=0}^{m-1} (s_i - t_{x-m+i+1})^2 \cdot s_i \cdot t_i $。这样就可以得到答案了。

 

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#include
#define ALL(x) (x).begin(),(x).end()
#define ll long long
#define db double
#define ull unsigned long long
#define pii_ pair
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "< 
\\

[[https://codeforces.com/problemset/problem/1334/G|CF1334G]]

在普通匹配的基础上添加条件 $p(s_i) = t_i$ 时也算匹配。$p$ 是题目给的一个置换。

同样不满足传递性，因此只能用 $\text{FFT}$ 匹配。

 
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include
#define ALL(x) (x).begin(),(x).end()
#define ll long long
#define db double
#define ull unsigned long long
#define pii_ pair
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<