前置知识
概述
FFT 可以在 $\mathcal O\left(n \log n\right)$ 解决几乎所有字符串匹配问题。但在解决复杂字符串匹配问题时，可能要做 $2$ 到 $3$ 次 FFT 和 IFFT。
普通字符串匹配
给定 $S$ 和 $T$，长度分别为 $m$ 和 $n$。求 $S$ 在 $T$ 中所有出现位置。
（本文中字符串下标均从 $1$ 开始）
现在我们的目标是使 $S$ 和 $T$ 的匹配变成卷积的形式。
设 $S_i$ 表示 $S$ 的第 $i$ 个字符，$T_i$ 同理。
设 $f\left(x, y\right) = \left(S_x - T_y\right)^2$。仅当 $f\left(x, y\right) = 0$ 时，$S$ 的第 $x$ 位才和 $T$ 的第 $y$ 位匹配。
设 $g\left(x\right)$ 表示 $S$ 是否在 $T$ 的第 $x$ 位出现。
$$g\left(x\right) = \sum\limits_{i = 1}^mf\left(i, x + i - 1\right)$$
仅当 $g\left(x\right) = 0$ 时，$S$ 在 $T$ 的第 $x$ 位出现。
接下来展开 $g\left(x\right)$：
$$ \begin{aligned} g\left(x\right) &= \sum\limits_{i = 1}^m\left(A_i - B_{x + i - 1}\right)^2\\ &= \sum\limits_{i = 1}^m{A_i}^2 - \sum\limits_{i = 1}^m2A_iB_{x + i - 1} + \sum\limits_{i = 1}^m{B_{x + i - 1}}^2 \end{aligned} $$
设 $C_i = A_{m - i +1}$：
$$ \begin{aligned} g\left(x\right) &= \sum\limits_{i = 1}^m{A_i}^2 + \sum\limits_{i = 1}^m{B_i}^2 - \sum\limits_{i = 1}^m2C_{m - i + 1}B_{x + i - 1}\\ &= \sum\limits_{i = 1}^m{A_i}^2 + \sum\limits_{i = 1}^m{B_i}^2 - \sum\limits_{i + j = m + x}2C_iB_j \end{aligned} $$
前两项可以预处理，最后一项可以 FFT。
带通配符的字符串的匹配
给出两个带有星号通配符的 $A$ 和 $B$，其中星号代表这里可以匹配任何字符，例如：
aa*b可以跟aacb和aaqb等等匹配。求 $A$ 在 $B$ 所有出现的位置。
定义通配符 * 用 $0$ 代替。
此时，设 $f\left(x, y\right) = S_x T_y \left(S_x - T_y\right)^2$。
这样，若 $S_x$ 或 $T_y$ 为通配符 $0$，则乘出来一定是 $0$。
把这个式子代入到 $g\left(x\right)$ 中展开一下：
$$ \begin{aligned} g\left(x\right) &= \sum\limits_{i = 1}^mA_iB_{x + i - 1}\left(A_i - B_{x + i - 1}\right)^2\\ &=\sum\limits_{i = 1}^mA_iB_{x + i - 1}\left({A_i}^2 - 2A_iB_{x + i - 1} - {B_{x + i - 1}}^2\right)\\ &=\sum\limits_{i = 1}^m{A_i}^3B_{x + i - 1} - \sum\limits_{i = 1}^m2{A_i}^2{B_{x + i - 1}}^2 + \sum\limits_{i = 1}^mA_i{B_{x + i - 1}}^3\\ &=\sum\limits_{i = 1}^m{C_{m - i + 1}}^3B_{x + i - 1} - \sum\limits_{i = 1}^m2{C_{m - i + 1}}^2{B_{x + i - 1}}^2 + \sum\limits_{i = 1}^mC_{m - i + 1}{B_{x + i - 1}}^3\\ &=\sum\limits_{i + j = m + x}{C_i}^3B_j - \sum\limits_{i + j = m + x}2{C_i}^2{B_j}^2 + \sum\limits_{i + j = m + x}C_i{B_j}^3 \end{aligned} $$
于是 $3$ 次 FFT + $3$ 次 IFFT。
但其实可以在三次 FFT 之后，在点值表示法下计算好，再一次 IFFT 计算回去。
struct Complex{double r,i;Complex()=default;Complex(double x,double y):r(x),i(y){}Complex operator+(Complex const&b)const{return Complex(r+b.r,i+b.i);}Complex operator-(Complex const&b)const{return Complex(r-b.r,i-b.i);}Complex operator*(Complex const&b)const{return Complex(r*b.r-i*b.i,r*b.i+i*b.r);}Complex operator/(Complex const&b)const{double t=b.r*b.r+b.i*b.i;return Complex((r*b.r+i*b.i)/t,(i*b.r-r*b.i)/t);}Complex operator+=(Complex const&b){return*this=*this+b;}Complex operator-=(Complex const&b){return*this=*this-b;}Complex operator*=(Complex const&b){return*this=*this*b;}Complex operator/=(Complex const&b){return*this=*this/b;}};
void FFT(vector<Complex>& f, tp n, tp type) {
double pi2 = acos(-1) * 2;
for (tp i = 0, k = 0; i < n; ++i) {
if (i < k) swap(f[i], f[k]);
for (tp j = n / 2; (k ^= j) < j; j /= 2);
}
for (tp p = 2; p <= n; p *= 2) {
tp m = p / 2;
Complex w(cos(pi2 / p), type * sin(pi2 / p));
for (tp k = 0; k < n; k += p) {
Complex g(1, 0);
for (tp l = k; l < k + m; ++l) {
Complex t = g * f[m + l];
f[m + l] = f[l] - t;
f[l] += t;
g *= w;
}
}
}
if (type == 1) return;
for (tp i = 0; i < n; ++i) f[i].r /= n;
for (tp i = 0; i < n; ++i) f[i].i /= n;
}
double sqr(double x) { return x * x; }
bool equal(double x) { return abs(x) <= 0.3; }
double trans(char c) { return c == '*' ? 0 : c - 'a' + 1; }
double cube(double x) { return x * x * x; }
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n, m, k = 1, cnt = 0; bin >> n >> m; --n; --m;
string s1, s2; bin >> s1 >> s2;
while (k <= n + m) k *= 2;
vector<Complex> a(k), b(k), c(k);
for (tp i = 0; i <= n; ++i) a[i].r = cube(trans(s1[i]));
for (tp i = 0; i <= m; ++i) b[i].r = trans(s2[m - i]);
FFT(a, k, 1); FFT(b, k, 1);
for (tp i = 0; i < k; ++i) c[i] += a[i] * b[i];
for (tp i = 0; i < k; ++i) a[i].r = b[i].r = a[i].i = b[i].i = 0;
for (tp i = 0; i <= n; ++i) a[i].r = sqr(trans(s1[i]));
for (tp i = 0; i <= m; ++i) b[i].r = sqr(trans(s2[m - i]));
FFT(a, k, 1); FFT(b, k, 1);
for (tp i = 0; i < k; ++i) c[i] -= a[i] * b[i] * Complex(2, 0);
for (tp i = 0; i < k; ++i) a[i].r = b[i].r = a[i].i = b[i].i = 0;
for (tp i = 0; i <= n; ++i) a[i].r = trans(s1[i]);
for (tp i = 0; i <= m; ++i) b[i].r = cube(trans(s2[m - i]));
FFT(a, k, 1); FFT(b, k, 1);
for (tp i = 0; i < k; ++i) c[i] += a[i] * b[i];
FFT(c, k, -1);
for (tp i = n; i <= m; ++i) cnt += equal(c[i].r);
bin << cnt << '\n';
for (tp i = m; i >= n; --i) {
if (equal(c[i].r)) bin << m - i + 1 << ' ';
}
bin << '\n';
}
Lightwhite · 2023-11-02 16:31
6