洛谷4173 残缺的字符串

$$ \text{这东西好神奇啊}qwq \\ \text{求出字符串}B\text{在字符串}A\text{中所有出现的位置。} \\ \text{设字符串下标均从0开始} \\ \text{设}A_x\text{表示}A\text{的第}x\text{个字符。} \\ \text{来定义一个神奇的函数，称之为匹配函数} \\ \text{设}m\text{为}B\text{串的长度} \\ P\left( x \right) =\sum_{0\le i<m}{\left( \begin{array}{c} A_{x-m+1+i}-B_i\\ \end{array} \right) ^2} \\ \text{注意到这个函数当且仅当字符串}B\text{出现在串}A\text{以}x\text{结尾的位置时才为}0 \\ \text{暴力计算起来仍然是}O\left( n^2 \right) \text{的} \\ \text{考虑拆开} \\ P\left( x \right) =\sum_{0\le i<m}{\begin{array}{c} B_i^2+A_{x-m+1+i}^2-2B_iA_{x-m+1+i}\\ \end{array}} \\ =\sum_{0\le i<m}{B_i^2}+\sum_{0\le i<m}{A_{x-m+1+i}^2}-2\sum_{0\le i<m}{B_iA_{x-m+1+i}} \\ \text{前两个求和符号可以直接计算。} \\ \text{第三个怎么搞？} \\ \text{设}T=B^R,\text{即}T\text{是}B\text{的反串。} \\ \text{所以存在}T_x=B_{m-x-1} \\ \text{故}P\left( x \right) =\sum_{0\le i<m}{T_i^2}+\sum_{0\le i<m}{A_{x-m+1+i}^2}-2\sum_{0\le i<m}{T_{m-i-1}A_{x-m+1+i}} \\ \text{注意到一个细节，}\left( m-i-1 \right) +\left( x-m+1+i \right) =x \\ \text{所以我们可以强行凑成卷积} \\ \sum_{0\le i<m}{T_{m-i-1}A_{x-m+1+i}} \\ =\sum_{0<m-i\le m}{T_{m-i-1}A_{x-m+1+i}} \\ =\sum_{0<i\le m}{T_{i-1}A_{x-i+1}} \\ =\sum_{-1<i-1\le m-1}{T_{i-1}A_{x-i+1}} \\ =\sum_{0\le i\le m-1}{T_iA_{x-i}} \\ =\sum_{i+j=x}{T_iA_j} \\ P\left( x \right) =\sum_{0\le i<m}{T_i^2}+\sum_{0\le i<m}{A_{x-i}^2}-2\sum_{i+j=x}{T_iA_j} \\ \text{当}x\ge m-\text{1的时候,}\sum_{0\le i\le m-1}{T_iA_{x-i}}=\sum_{0\le i\le x}{T_iA_{x-i}} \\ \text{然后可以卷积了}qwq \\ \text{带通配符怎么办?} \\ \text{设通配符的字符代码为}0 \\ \text{匹配函数变成}P\left( x \right) =\sum_{0\le i<m}{\left( \begin{array}{c} A_{x-m+1+i}-B_i\\ \end{array} \right) ^2A_{x-m+1+i}B_i} \\ =\sum_{0\le i<m}{\left( B_i^2+A_{x-m+1+i}^2-2B_iA_{x-m+1+i} \right) A_{x-m+1+i}B_i} \\ =\sum_{0\le i<m}{B_{i}^{3}A_{x-m+1+i}}+\sum_{0\le i<m}{B_iA_{x-m+1+i}^3}-2\sum_{0\le i<m}{A_{x-m+1+i}^2B_i^2} \\ B_x=T_{m-x-1} \\ P\left( x \right) =\sum_{0\le i<m}{T_{m-i-1}^3A_{x-m+1+i}}+\sum_{0\le i<m}{T_{m-i-1}A_{x-m+1+i}^3}-2\sum_{0\le i<m}{A_{x-m+1+i}^2T_{m-i-1}^2} \\ P\left( x \right) =\sum_{i+j=x}{T_i^3A_j}+\sum_{i+j=x}{T_iA_j^3}-2\sum_{i+j=x}{A_i^2T_j^2} \\ \text{仍然大力卷积即可。} \\ $$

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t mod = 998244353;
const int_t g = 3;
const int_t LARGE = 1 << 20;
int_t power(int_t base, int_t index);
void transform(int_t* A, int_t size, int_t arg = 1);
int_t bitRev(int_t x, int_t size2) {
    int_t result = 0;
    for (int_t i = 1; i < size2; i++) {
        result |= (x & 1);
        x >>= 1;
        result <<= 1;
    }
    return result | (x & 1);
}
constexpr inline int_t upper2n(int_t x) {
    int_t result = 1;
    while (result < x) result *= 2;
    return result;
}
int main() {
    int n, m;
    static char As[LARGE], Bs[LARGE], Ts[LARGE];
    scanf("%d%d%s%s", &m, &n, Bs, As);
    std::reverse_copy(Bs, Bs + m, Ts);
    // cout << Ts << endl;
    static int_t A1[LARGE], A2[LARGE], A3[LARGE];
    static int_t T1[LARGE], T2[LARGE], T3[LARGE];
    for (int_t i = 0; i < n; i++) {
        A1[i] = As[i];
        if (As[i] == '*') A1[i] = 0;
        A2[i] = A1[i] * As[i];
        A3[i] = A2[i] * As[i];
    }
    for (int_t i = 0; i < m; i++) {
        T1[i] = Ts[i];
        if (Ts[i] == '*') T1[i] = 0;
        T2[i] = T1[i] * Ts[i];
        T3[i] = T2[i] * Ts[i];
    }
    int_t size = upper2n(n + m + 1);
    transform(A1, size);
    transform(A2, size);
    transform(A3, size);
    transform(T1, size);
    transform(T2, size);
    transform(T3, size);
    static int_t result[LARGE];
    for (int_t i = 0; i < size; i++) {
        result[i] = (T3[i] * A1[i] % mod + T1[i] * A3[i] % mod -
                     2 * A2[i] * T2[i] % mod + 3 * mod) %
                    mod;
    }
    transform(result, size, -1);
    for (int_t i = 0; i < size; i++) {
        result[i] = result[i] * power(size, -1) % mod;
        // cout << "pos " << i << " " << result[i] << endl;
    }
    std::vector<int> results;
    for (int_t i = 0; i < n; i++) {
        if (result[i] == 0 && (i - m + 2 >= 1)) {
            results.push_back(i - m + 2);
        }
    }
    printf("%d\n", (int)results.size());
    for (int x : results) printf("%d ", x);
    return 0;
}

int_t power(int_t base, int_t index) {
    const auto phi = mod - 1;
    index = (index % phi + phi) % phi;
    base = (base % mod + mod) % mod;
    int_t result = 1;
    while (index) {
        if (index & 1) result = result * base % mod;
        index >>= 1;
        base = base * base % mod;
    }
    return result;
}
void transform(int_t* A, int_t size, int_t arg) {
    int_t size2 = log2(size);
    for (int_t i = 0; i < size; i++) {
        int_t x = bitRev(i, size2);
        if (x > i) std::swap(A[i], A[x]);
    }
    for (int_t i = 2; i <= size; i *= 2) {
        int_t mr = power(g, arg * (mod - 1) / i);
        for (int_t j = 0; j < size; j += i) {
            int_t curr = 1;
            for (int_t k = 0; k < i / 2; k++) {
                int_t u = A[j + k];
                int_t t = A[j + k + i / 2] * curr % mod;
                A[j + k] = (u + t) % mod;
                A[j + k + i / 2] = (u - t + mod) % mod;
                curr = curr * mr % mod;
            }
        }
    }
}