用 FFT 解决（带通配符的）字符串匹配。
普通字符串匹配
设 $S$ 为模式串，$T$ 为文本串，$n=\lvert S \rvert,m=\lvert T \rvert$（字符串下标从 $0$ 开始）。
显然，两个字符串相同，当且仅当它们每一位都相同，这是一句废话。
我们联想到初中一年级的一句重要的话：**如果若干个非负数的和为 $0$，那么它们都为 $0$**。
和为 $0$ 正好对应了 每一位都相同，所以很容易得出这个 完全匹配函数（很重要！之后要考）
$$f(x)=\sum\limits_{i=0}^{n-1} (S_i-T_{x-n+i+1})^2$$
$f(x)$ 表示 $S$ 与 $T_{(x-n+1)\dots x}$ 的 匹配值 。
其中平方是为了保证每一项都是非负数。这样，只有每一项都为 $0$（即 $S_i=T_{x+i-1}$），$f(x)$ 才会为 $0$。
显然这个柿子不是很好化简，所以我们要对它进行一点点的变形。
什么柿子容易计算呢？当然是卷积，即：
$$f(x)=\sum\limits_{i+j=x} A_iB_j$$
然而之前那个柿子中，$i$ 和 $x-n+i+1$ 加起来显然不是一个定值。如何把这个 $i$ 消掉呢？
我们考虑把 $S$ 整个串反转，这样原来的 $i$ 就变成了 $n-i-1$。
于是变成：
$$f(x)=\sum\limits_{i=0}^{n-1} (S_{n-i+1}-T_{x-n+i+1})^2$$
两个下标相加：
$$(n-i+1)+(x-n+i+1)=x$$
好耶！消掉了！
于是那个柿子就可以写成：
$$f(x)=\sum\limits_{i+j=x}(S_i-T_j)^2$$
用完全平方公式拆开：
$$f(x)=\sum\limits_{i+j=x}S_i^2-2S_iT_j+T_j^2$$
显然第一项和第三项可以预处理得到，第二项就是 $S\cdot T$ 中 $x$ 次项的系数乘上 $-2$，只需要把 $S$ 和 $T$ 看成多项式，FFT 相乘即可。
复杂度 $O(n \log n)$。
带通配符的字符串匹配
通配符，即可以匹配任意字符的字符（当然也可以匹配通配符）。
显然这种问题 KMP 就无能为力了。然而，对于 FFT 做法，我们仍然可以用相似的思路解决。
我们发现，原来 完全匹配函数 为 $0$，当且仅当对应的两个字符相同。但是，现在有了通配符，条件应该改为满足以下两个中任意一个：
- 对应两个字符相同
- 对应两个字符中有任意一个是通配符
很容易想到设通配符为 $0$（当然其它任何字符都不能为 $0$）。完全匹配函数 就变成了：
$$f(x)=\sum\limits_{i=0}^{n-1} (S_i-T_{x-n+i+1})^2 \cdot S_iT_j$$
如果 $S_i=0$ 或 $T_i=0$，那么 $f(x)$ 仍然为 $0$。
老规矩，反转 $S$：
$$f(x)=\sum\limits_{i=0}^{n-1} (S_{n-i+1}-T_{x-n+i+1})^2 \cdot S_iT_j$$
化成卷积形式：
$$f(x)=\sum\limits_{i+j=x}(S_i-T_j)^2 \cdot S_iT_j$$
完全平方公式：
$$f(x)=\sum\limits_{i+j=x}S_i^3T_j-2S_i^2T_j^2+S_iT_j^3$$
看起来很复杂？但每一项还是卷积的形式，于是就用很多次 FFT 解决了。
复杂度 $O(n \log n)$。
例题
模板题
残缺的字符串
做法
就是模板题，按上面方法做就完了。
注意数组大小好好算，$eps$ 我取的 $1$ 过了。
常数有点大，吸氧能过。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| const double pi = acos(-1);
int T_, case_;
int n1, n2, n = 1, len = 0;
string s, t;
int S[MAXN], T[MAXN];
struct Complex {
double r, i;
Complex() { r = i = 0; }
Complex(double r_, double i_) :r(r_), i(i_) {};
Complex operator+(const Complex& x)const { return Complex(r + x.r, i + x.i); };
Complex operator-(const Complex& x)const { return Complex(r - x.r, i - x.i); };
Complex operator*(const Complex& x)const { return Complex(r * x.r - i * x.i, i * x.r + r * x.i); };
};
int rev[MAXN];
void FFT(Complex* a, int f) {
rep(i, n)if (i < rev[i])swap(a[i], a[rev[i]]);
repp(d, log2(n)) {
int l = 1 << d;
Complex wn = Complex(cos(2.0 * pi / l), f * sin(2.0 * pi / l));
for (int i = 0;i < n;i += l) {
Complex w = Complex(1, 0);
rep(j, l / 2) {
Complex t = w * a[i + j + l / 2], u = a[i + j];
a[i + j] = u + t;
a[i + j + l / 2] = u - t;
w = w * wn;
}
}
}
if (f == -1)rep(i, n)a[i].r /= n;
}
Complex a[MAXN], b[MAXN], ans[MAXN];
vector<int>v;
void solve() {
cin >> n1 >> n2 >> s >> t;
reverse(s.begin(), s.end());
while (n < n1 + n2)n *= 2, len++;
rep(i, n)rev[i] = (rev[i / 2] / 2 | ((i & 1) << (len - 1)));
rep(i, n1)S[i] = (isalpha(s[i]) ? s[i] - 'a' + 1 : 0);
rep(i, n2)T[i] = (isalpha(t[i]) ? t[i] - 'a' + 1 : 0);
rep(i, n)a[i] = Complex(S[i] * S[i] * S[i], 0), b[i] = Complex(T[i], 0);
FFT(a, 1), FFT(b, 1);
rep(i, n)ans[i] = a[i] * b[i];
rep(i, n)a[i] = Complex(S[i] * S[i], 0), b[i] = Complex(T[i] * T[i], 0);
FFT(a, 1), FFT(b, 1);
rep(i, n)ans[i] = ans[i] - Complex(2, 0) * a[i] * b[i];
rep(i, n)a[i] = Complex(S[i], 0), b[i] = Complex(T[i] * T[i] * T[i], 0);
FFT(a, 1), FFT(b, 1);
rep(i, n)ans[i] = ans[i] + a[i] * b[i];
FFT(ans, -1);
forr(i, n1 - 1, n2 - 1)if (fabs(ans[i].r) <= 1)v.pb(i - n1 + 2);
if (v.empty()) {
cout << 0;
return;
}
cout << v.size() << endl;
rep(i, v.size())cout << v[i] << ' ';
}
|
练习题
CF528D Fuzzy Search
题目大意
有两个字符串 $S,T$，长度分别为 $n,m$，字符集为 ${A,C,G,T}$，和一个整数 $k$。
我们称 $S$ 在 $T$ 的第 $i$ 位出现了，当且仅当把 $S$ 的首字符和 $T$ 的第 $i$ 个字符对齐后，$S$ 中的每一个字符能够在 $T$ 中找到一个位置偏差不超过 $k$ 的相同字符。
即对于所有的 $j \in[1,n]$，都存在一个 $p \in [1,m]$ 使得 $|(i+j-1)-p| \leq k$ 且 $S_p=T_j$ 。
请求出 $S$ 在 $T$ 中出现的次数。
做法
首先把四种字母分开来考虑，最后取四个集合的交即可。
接下来假设只考虑字母 A，其余三个同理。
先把 $S$ 和 $T$ 除了 A 的部分都去掉（即空白），其余位置涂色。
接下来对 $T$ 处理：由于 $T$ 中的一个 A（假设在第 $i$ 位）可以影响到 $[i-k,i+k]$ 这些位置，所以把这些位置全都涂色。
接下来直接匹配即可。对于 $S$ 上有颜色的位置，$T$ 对应位置一定要有颜色；而对于 $S$ 上空白的位置，$T$ 对应位置可以有颜色，也可以是空白。
于是把 $T$ 的涂色部分看成 $1$，空白部分看成 $2$，$S$ 的涂色部分看成 $1$，空白部分看成 $0$（即通配符）。
复杂度 $O(n \log n)$。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| const double pi = acos(-1);
int T_, case_;
int n1, n2, n = 1, len = 0, k;
string s, t;
int S[MAXN], T[MAXN];
struct Complex {
double r, i;
Complex() { r = i = 0; }
Complex(double r_, double i_) :r(r_), i(i_) {};
Complex operator+(const Complex& x)const { return Complex(r + x.r, i + x.i); };
Complex operator-(const Complex& x)const { return Complex(r - x.r, i - x.i); };
Complex operator*(const Complex& x)const { return Complex(r * x.r - i * x.i, i * x.r + r * x.i); };
};
int rev[MAXN];
void FFT(Complex* a, int f) {
rep(i, n)if (i < rev[i])swap(a[i], a[rev[i]]);
repp(d, log2(n)) {
int l = 1 << d;
Complex wn = Complex(cos(2.0 * pi / l), f * sin(2.0 * pi / l));
for (int i = 0;i < n;i += l) {
Complex w = Complex(1, 0);
rep(j, l / 2) {
Complex t = w * a[i + j + l / 2], u = a[i + j];
a[i + j] = u + t;
a[i + j + l / 2] = u - t;
w = w * wn;
}
}
}
if (f == -1)rep(i, n)a[i].r /= n;
}
Complex a[MAXN], b[MAXN], ans[MAXN];
char C[] = { 'A','C','G','T' };
int d;
int sum[MAXN], SUM = 0;
void solve() {
cin >> n2 >> n1 >> k >> t >> s;
reverse(s.begin(), s.end());
while (n < n1 + n2)n *= 2, len++;
rep(i, n)rev[i] = (rev[i / 2] / 2 | ((i & 1) << (len - 1)));
rep(c, 4) {
rep(i, n1)S[i] = (s[i] == C[c]);
d = 0;
rep(i, min(k, n2))d += (t[i] == C[c]);
rep(i, n2) {
if (i + k < n2)d += (t[i + k] == C[c]);
T[i] = (d > 0 ? 1 : 2);
if (i - k >= 0)d -= (t[i - k] == C[c]);
}
rep(i, n)a[i] = Complex(S[i] * S[i] * S[i], 0), b[i] = Complex(T[i], 0);
FFT(a, 1), FFT(b, 1);
rep(i, n)ans[i] = a[i] * b[i];
rep(i, n)a[i] = Complex(S[i] * S[i], 0), b[i] = Complex(T[i] * T[i], 0);
FFT(a, 1), FFT(b, 1);
rep(i, n)ans[i] = ans[i] - Complex(2, 0) * a[i] * b[i];
rep(i, n)a[i] = Complex(S[i], 0), b[i] = Complex(T[i] * T[i] * T[i], 0);
FFT(a, 1), FFT(b, 1);
rep(i, n)ans[i] = ans[i] + a[i] * b[i];
FFT(ans, -1);
forr(i, n1 - 1, n2 - 1)if (fabs(ans[i].r) <= 1)sum[i - n1 + 1]++;
}
rep(i, n2 - n1 + 1)if (sum[i] == 4)SUM++;
cout << SUM;
}
|