快速傅里叶变换：应用

大整数乘法（高精度乘法）

假设有两个整数 $a = 537, b = 721$ 。 $a, b$ 的每一位可以视为多项式 $A (x), B (x)$ 的系数：

A (x) = 5 x^{2} + 3 x + 7, B (x) = 7 x^{2} + 2 x + 1

计算 $C (x) = A (x) \cdot B (x)$ ：

C (x) = 35 x^{4} + 31 x^{3} + 60 x^{2} + 17 x + 7

提取 $C (x)$ 的系数：

{35, 31, 60, 17, 7}

从右往左，逢 $10$ 进 $1$ ：

{3, 8, 7, 1, 7, 7}

这样就能得到 $537 \times 721$ 的结果是 $387177$ 。

多项式乘法由 FFT 进行。如果 $a$ 和 $b$ 是 $n$ 位整数，则总时间复杂度是 $O (n \log n)$ 。

整数乘法和多项式乘法具有高度的相似性。

一个整数可以分解为它的位值的和。例如，整数 $123$ 可以分解为 $1 \times 10^{2} + 2 \times 10 + 3$ 。

设 $a = \overset{―}{a_{2} a_{1} a_{0}}$ ， $b = \overset{―}{b_{2} b_{1} b_{0}}$ ，则

\begin{aligned} a \times b \\ = & (a_{2} \cdot 10^{2} + a_{1} \cdot 10 + a_{0}) \cdot (b_{2} \cdot 10^{2} + b_{1} \cdot 10 + b_{0}) \\ = & a_{2} b_{2} \cdot 10^{4} + (a_{2} b_{1} + a_{1} b_{2}) \cdot 10^{3} + (a_{2} b_{0} + a_{1} b_{1} + a_{0} b_{2}) \cdot 10^{2} + (a_{1} b_{0} + a_{0} b_{1}) \cdot 10 + a_{0} b_{0} \end{aligned}

设 $A (x) = a_{2} x^{2} + a_{1} x + a_{0}$ ， $B (x) = b_{2} x^{2} + b_{1} x + b_{0}$ ，则

\begin{aligned} A (x) \times B (x) \\ = & (a_{2} x^{2} + a_{1} x + a_{0}) \cdot (b_{2} x^{2} + b_{1} x + b_{0}) \\ = & a_{2} b_{2} \cdot x^{4} + (a_{2} b_{1} + a_{1} b_{2}) \cdot x^{3} + (a_{2} b_{0} + a_{1} b_{1} + a_{0} b_{2}) \cdot x^{2} + (a_{1} b_{0} + a_{0} b_{1}) \cdot x + a_{0} b_{0} \end{aligned}

可以看出整数乘法和多项式乘法基本是同构的。整数乘法在最后一步需要额外处理进位。

模板

cpp

// put FFT algorithm template here

vector<Comp> string_to_vector(const string& s) {
    vector<Comp> result;
    for (auto rit = s.rbegin(); rit != s.rend(); ++rit) {
        result.push_back(*rit - '0');
    }
    return result;
}

string vector_to_string(const vector<Comp>& v) {
    string result;
    for (const Comp& c : v) {
        result += to_string(int(c.real())) + " ";
    }
    return result;
}

string upgrade(vector<Comp>& a) {
    string result;
    int carry = 0;
    for (auto i : a) {
        int num = int(real(i) + 0.5) + carry;
        carry = num / 10;
        result += (num % 10) + '0';
    }
    while (!result.empty() && result.back() == '0') {
        result.pop_back();
    }
    reverse(result.begin(), result.end());
    return result.empty() ? "0" : result;
}

string multiply_big_integers(const string& s1, const string& s2) {
    vector<Comp> a = string_to_vector(s1);
    vector<Comp> b = string_to_vector(s2);
    vector<Comp> c = multiply(a, b);
    return vector_to_string(c);
}

int main() {
    string num1, num2;
    cin >> num1 >> num2;

    string product = multiply_big_integers(num1, num2);
    cout << product << endl;
    
    return 0;
}

朴素字符串匹配

设有两个字符串 $text$ ， $pattern$ 的长度分别为 $n, m (n \geq m)$ ，并只包含小写字母 $a \dots z$ 。问 $pattern$ 在 $text$ 中出现了几次，以及所有的出现位置。

该问题可使用 FFT 在 $O (n \log n)$ 的复杂度下解决。

约定 $str |_{a}^{b}$ 表示从 $str [a]$ 到 $str [b]$ 的子串。

首先将 $text$ 和 $pattern$ 的所有字母都映射成数字（ $a \to 1, b \to 2, \dots$ ），得到两个整型数组 $A$ 和 $B$ 。

\begin{aligned} text & \to A : {A_{0}, A_{1}, \dots, A_{n - 1}} \\ pattern & \to B : {B_{0}, B_{1}, \dots, B_{m - 1}} \end{aligned}

容易发现

{(A_{i} - B_{j})}^{2} = {\begin{cases} 0, & A_{i} = B_{j} \\ > 0, & A_{i} \neq B_{j} \end{cases}

进而构造

\begin{aligned} P_{k} & = (A_{k} - B_{0})^{2} + (A_{k + 1} - B_{1})^{2} + \dots + (A_{k + m - 1} - B_{m - 1})^{2} \\ = \sum_{i = 0}^{m - 1} {(A_{k + i} - B_{i})}^{2} \\ = {\begin{cases} 0, & text |_{k}^{k + m - 1} = pattern \\ > 0, & text |_{k}^{k + m - 1} \neq pattern \end{cases} \end{aligned}

因此可以利用 $P_{k}$ 判断 $pattern$ 是否出现在 $text$ 的第 $k$ 位。

展开 $P_{k}$ ：

\begin{aligned} P_{k} & = \sum_{i = 0}^{m - 1} {(A_{k + i} - B_{i})}^{2} \\ = \sum_{i = 0}^{m - 1} (A_{k + i}^{2} + B_{i}^{2} - 2 A_{k + i} B_{i}) \\ = \sum_{i = 0}^{m - 1} A_{k + i}^{2} + \sum_{i = 0}^{m - 1} B_{i}^{2} - 2 \sum_{i = 0}^{m - 1} A_{k + i} B_{i} \end{aligned}

将数组 $B$ 反转得到 $\tilde{B}$ ，有 $B_{i} = {\tilde{B}}_{m - i - 1}$ 。代入得

P_{k} = \sum_{i = 0}^{m - 1} A_{k + i}^{2} + \sum_{i = 0}^{m - 1} B_{i}^{2} - 2 \sum_{i = 0}^{m - 1} A_{k + i} {\tilde{B}}_{m - i - 1}

分析该式的三项：

$\sum_{i = 0}^{m - 1} A_{k + i}^{2}$ 可以通过前缀和技巧实现 $O (n)$ 预处理， $O (1)$ 查询；
$\sum_{i = 0}^{m - 1} B_{i}^{2}$ 是常数，可以直接 $O (n)$ 预处理；
$\sum_{i = 0}^{m - 1} A_{k + i} {\tilde{B}}_{m - i - 1}$ 是卷积式，可以通过 FFT 实现 $O (n \log n)$ 预处理， $O (1)$ 查询。

对于第 3 项，更具体地说：

构造多项式

A (x) = A_{0} + A_{1} x + A_{2} x^{2} + \dots + A_{n - 1} x^{n - 1} \tilde{B} (x) = {\tilde{B}}_{0} + {\tilde{B}}_{1} x + {\tilde{B}}_{2} x^{2} + \dots + {\tilde{B}}_{m - 1} x^{m - 1}

利用 FFT 可以 $O (n \log n)$ 得出多项式 $C (x) = A (x) \cdot \tilde{B} (x)$ 的系数向量。易知 $C (x)$ 中 $x^{k + m - 1}$ 前的系数为 $\sum_{i = 0}^{m - 1} A_{k + i} {\tilde{B}}_{m - i - 1}$ ，这正是我们想要的第 3 项。

依次计算 $P_{k} (k = 0, 1, 2, \dots, n - m)$ ，当得到 $0$ 时说明 $pattern$ 出现在 $text$ 的第 $k$ 位。

TIP

用 FFT 实现的字符串匹配，其效率并不是最优的，并且常数很大。

KMP 可以在 $O (n + m)$ 的线性复杂度下解决字符串匹配问题。

模板

cpp

// put FFT algorithm template here

vector<int> stringMatchingFFT(const string& text, const string& pattern) {
    int n = text.size(), m = pattern.size();
    
    vector<Comp> A(n), B(m);
    long long sum_AA[n], sum_BB = 0;

    for (int i = 0; i < n; i ++) {
        int value = text[i] - 'a' + 1;
        A[i] = value;
        sum_AA[i] = value * value;
        if (i) {
            sum_AA[i] += sum_AA[i - 1];
        }
    }

    for (int i = 0; i < m; i ++) {
        int value = pattern[i] - 'a' + 1;
        B[m - i - 1] = value;
        sum_BB += value * value;
    }

    vector<Comp> C = multiply(A, B);

    vector<int> matches;
    for (int i = 0; i <= n - m; i ++) {
        long long
            part1 = sum_AA[i + m - 1] - (i ? sum_AA[i - 1] : 0),
            part2 = sum_BB,
            part3 = C[i + m - 1].real();
        if (part1 + part2 - 2 * part3 == 0)
            matches.push_back(i);
    }
    
    return matches;
}

int main() {
    string text, pattern;
    cin >> text >> pattern;
    
    vector<int> matches = stringMatchingFFT(text, pattern);

    cout << matches.size() << "\n";
    for (int i : matches) cout << i << " ";
    cout << "\n";

    return 0;
}

带通配符的字符串匹配

设有两个字符串 $text$ ， $pattern$ 的长度分别为 $n, m (n \geq m)$ ，并只包含小写字母 $a \dots z$ 和通配符 $*$ （可与任意字符匹配）。问 $pattern$ 在 $text$ 中的匹配次数和所有匹配位置。

令通配符 $*$ 映射到 $0$ ，则

{(A_{i} - B_{j})}^{2} \cdot A_{i} \cdot B_{j} = {\begin{cases} 0, & A_{i} = B_{j} \\ > 0, & A_{i} \neq B_{j} \end{cases}

\begin{aligned} P_{k} & = \sum_{i = 0}^{m - 1} {(A_{k + i} - B_{i})}^{2} \cdot A_{k + i} \cdot B_{i} \\ = \sum_{i = 0}^{m - 1} (A_{k + i}^{2} + B_{i}^{2} - 2 A_{k + i} B_{i}) \cdot A_{k + i} \cdot B_{i} \\ = \sum_{i = 0}^{m - 1} A_{k + i}^{3} B_{i} + \sum_{i = 0}^{m - 1} A_{k + i} B_{i}^{3} - 2 \sum_{i = 0}^{m - 1} A_{k + i}^{2} B_{i}^{2} \\ = \sum_{i = 0}^{m - 1} A_{k + i}^{3} {\tilde{B}}_{m - i - 1} + \sum_{i = 0}^{m - 1} A_{k + i} {\tilde{B}}_{m - i - 1}^{3} - 2 \sum_{i = 0}^{m - 1} A_{k + i}^{2} {\tilde{B}}_{m - i - 1}^{2} \end{aligned}

构造多项式

\begin{aligned} A_{k} (x) & = A_{0}^{k} + A_{1}^{k} x + A_{2}^{k} x^{2} + \dots + A_{n - 1}^{k} x^{n - 1} \\ {\tilde{B}}_{k} (x) & = {\tilde{B}}_{0}^{k} + {\tilde{B}}_{1}^{k} x + {\tilde{B}}_{2}^{k} x^{2} + \dots + {\tilde{B}}_{m - 1}^{k} x^{m - 1} \end{aligned}

$\sum_{i = 0}^{m - 1} A_{k + i}^{3} {\tilde{B}}_{m - i - 1}$ 是 $A_{3} (x) \cdot {\tilde{B}}_{1} (x)$ 中 $x^{k + m - 1}$ 前的系数；
$\sum_{i = 0}^{m - 1} A_{k + i} {\tilde{B}}_{m - i - 1}^{3}$ 是 $A_{1} (x) \cdot {\tilde{B}}_{3} (x)$ 中 $x^{k + m - 1}$ 前的系数；
$\sum_{i = 0}^{m - 1} A_{k + i}^{2} {\tilde{B}}_{m - i - 1}^{2}$ 是 $A_{2} (x) \cdot {\tilde{B}}_{2} (x)$ 中 $x^{k + m - 1}$ 前的系数。

进行三次 FFT 即可。

模板

cpp

// put FFT algorithm template here

vector<int> stringMatchingFFT(const string& text, string pattern) {
    int n = text.size(), m = pattern.size();
    
    vector<Comp> A1, A2, A3, B1, B2, B3;

    for (auto i : text) {
        int value = i == '*' ? 0 : i - 'a' + 1;
        A1.push_back(value);
        A2.push_back(value * value);
        A3.push_back(value * value * value);
    }

    reverse(pattern.begin(), pattern.end());

    for (auto i : pattern) {
        int value = i == '*' ? 0 : i - 'a' + 1;
        B1.push_back(value);
        B2.push_back(value * value);
        B3.push_back(value * value * value);
    }

    vector<Comp> part1 = multiply(A3, B1);
    vector<Comp> part2 = multiply(A1, B3);
    vector<Comp> part3 = multiply(A2, B2);

    vector<int> matches;
    for (int i = 0; i <= n - m; i ++) {
        if (part1[i + m - 1].real() + part2[i + m - 1].real() - part3[i + m - 1].real() * 2 == 0)
            matches.push_back(i);
    }
    
    return matches;
}

int main() {
    string text, pattern;
    cin >> text >> pattern;
    
    vector<int> matches = stringMatchingFFT(text, pattern);

    cout << matches.size() << "\n";
    for (int i : matches) cout << i << " ";
    cout << "\n";

    return 0;
}

同余

组合数学

数值分析

多项式

圆锥曲线

快速傅里叶变换：应用

大整数乘法（高精度乘法）

模板

朴素字符串匹配

模板

带通配符的字符串匹配

模板

快速傅里叶变换：应用

大整数乘法（高精度乘法） ​

模板 ​

朴素字符串匹配 ​

模板 ​

带通配符的字符串匹配 ​

模板 ​

大整数乘法（高精度乘法）

模板

朴素字符串匹配

模板

带通配符的字符串匹配

模板