2019.01.26 Codeforces 528D. Fuzzy Search (FFT)

题目概述

本题的题意是给出一个长度为 $n$ 的文本串 $s$，一个长度为 $m$ 的模式串 $t$，以及允许 $k$ 次错误匹配的限制，求模式串在文本串中的出现次数。其中，错误匹配指的是允许在 $t$ 中最多更改 $k$ 个字符（包括删减和增加）以达到与文本串 $s$ 的匹配。

解题思路

本题的数据范围比较小，可以通过暴力枚举的方法解决，时间复杂度为 $O(nm^2k^2)$，但是很容易超时。

因此，可以考虑使用一些高级算法来提升效率。例如，本题可以使用字符串编码算法，将字符串转化为数字序列，然后利用 FFT 进行匹配。对于字符串的编码，可以使用类似于进制转换的方法，将字符串转化为 $k + 1$ 的一次多项式，其中第 $i$ 项的系数表示匹配错误数为 $i$ 时的字符串匹配程度。然后，利用 FFT 对两个多项式进行卷积操作，即可得到在 $k$ 次错误匹配的情况下的匹配程度。最后，再遍历每个位置的匹配程度，即可得到答案。

代码实现

详见程序注释：

// 头文件
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <complex>
using namespace std;

// 常量
const int MAXN = 2e5 + 5;
const double PI = acos(-1.0);

// 变量
int n, m, k;
char s[MAXN], t[MAXN];
int ans;

// FFT操作
inline void fft(complex<double> *a, int n, int inv = 1) {
    // 位逆序置换
    for(int i = 0, j = 0; i < n; i++) {
        if(i < j) swap(a[i], a[j]);
        for(int k = n >> 1; (j ^= k) < k; k >>= 1);
    }
    // 计算
    for(int i = 2; i <= n; i <<= 1) {
        int m = i >> 1;
        complex<double> wn(cos(2 * PI / i), inv * sin(2 * PI / i));
        for(int j = 0; j < n; j += i) {
            complex<double> w(1, 0);
            for(int k = 0; k < m; k++, w *= wn) {
                complex<double> x = a[j + k], y = w * a[j + k + m];
                a[j + k] = x + y, a[j + k + m] = x - y;
            }
        }
    }
}

// 长整数乘法
void mul(int *a, int n, int *b, int m, int *c) {
    complex<double> tmpa[MAXN], tmpb[MAXN], tmpr[MAXN], tmps[MAXN], tmpt[MAXN], tmpu[MAXN], tmpv[MAXN];
    int p = 1;
    while(p < n + m + 1) p <<= 1;
    memset(tmpa, 0, sizeof(tmpa));
    memset(tmpb, 0, sizeof(tmpb));
    for(int i = 0; i <= n; i++) tmpa[i] = a[i];
    for(int i = 0; i <= m; i++) tmpb[i] = b[i];
    fft(tmpa, p); fft(tmpb, p);
    for(int i = 0; i < p; i++) tmpr[i] = tmpa[i] * tmpb[i];
    fft(tmpr, p, -1);
    for(int i = 0; i <= n + m; i++) c[i] = (int)(tmpr[i].real() + 0.22);
}

// 多项式加法
void add(int *a, int n, int *b, int m, int *res) {
    memset(res, 0, sizeof(int) * (n + m + 1));
    for(int i = 0; i <= n; i++) res[i] += a[i];
    for(int i = 0; i <= m; i++) res[i] += b[i];
}

// 主函数
int main() {
    // 读入
    scanf("%s%s%d", s + 1, t + 1, &k);
    n = strlen(s + 1);
    m = strlen(t + 1);
    // 数据初始化
    int dp[MAXN] = {0};
    int fac[MAXN] = {0};
    int f[MAX(2 * k + 1, m) + 1] = {0};
    int g[MAX(2 * k + 1, m) + 1] = {0};
    // 循环计算匹配程度
    for(int i = 1; i <= n; i++) {
        // 计算 $s$ 的多项式表示
        memset(f, 0, sizeof(f));
        for(int j = max(0, i - k); j <= i; j++) {
            f[i - j] = (s[j] == t[i - j]) ? 1 : -1;
        }
        // 计算 $t$ 的多项式表示
        g[0] = 1;
        for(int j = 1; j <= m; j++) {
            g[j] = (t[j] == s[i - m + j]) ? 1 : -1;
        }
        // 计算卷积
        memset(dp, 0, sizeof(dp));
        for(int j = 0; j <= k && j <= i; j++) {
            mul(f + j, m - i + j + k - m, g, m, fac);
            add(dp + j, m + k - i + j, fac, m, dp + j);
        }
        // 统计答案
        ans += dp[k];
    }
    // 输出答案
    printf("%d\n", ans);
    return 0;
}

时间复杂度

由于本题利用了 FFT 算法进行求解，时间复杂度为 $O(n \log n)$。但是由于还进行了多项式乘法等操作，因此具体的常数项还需与 $k$、$m$ 等因素有关。

总结

本题主要考察了利用 FFT 求解多项式卷积的能力。因此，建议在做标准的 FFT 求解多项式卷积问题之后，再尝试做这道题。