题目链接：Luogu 4173

很久很久以前，在你刚刚学习字符串匹配的时候，有两个仅包含小写字母的字符串 $A$ 和 $B$，其中 $A$ 串长度为 $m$，$B$ 串长度为 $n$。可当你现在再次碰到这两个串时，这两个串已经老化了，每个串都有不同程度的残缺。

你想对这两个串重新进行匹配，其中 $A$ 为模板串，那么现在问题来了，请回答，对于 $B$ 的每一个位置 $i$，从这个位置开始连续 $m$ 个字符形成的子串是否可能与 $A$ 串完全匹配？

数据范围：$1 \le m \le n \le 3 \times 10 ^ {5}$。

Solution

字符串匹配问题可以使用 $\text{FFT}$ 解决。

首先我们定义通配符为 * 为 $0$，其余字母分别按顺序标号为 $1$ 到 $26$。

我们对于两个长度相同的字符串 $A, B$ 构造匹配函数：

$$ \begin{align*} F(A, B) & = \sum_{i = 0} ^ {n - 1} (A_{i} - B_{i}) ^ {2} A_{i} B_{i} \\ & = \sum_{i = 0} ^ {n - 1} \left ({A_{i}} ^ {3} B_{i} - 2 {A_{i}} ^ {2} {B_{i}} ^ {2} + A_{i} {B_{i}} ^ {3} \right ) \end{align*} $$

两个字符串完全匹配的充要条件是 $F(A, B) = 0$。

这明显是一个卷积形式，把 $A$ 翻转后 $\text{FFT}$ 求出所有值为 $0$ 的下标。

吐槽：竟然 $\text{NTT}$ 也能通过本题，出题人怎么连常用模数都没卡呀……

时间复杂度：$\mathcal O(n \log n)$，自带超大常数（需要 $7 \sim 9$ 次 $\text{FFT}$）。

Code

/* 此处省略多项式模板 */

const int N = 3e5 + 5;

int n, m;
char s[N], t[N];

Vec solve(Vec A, Vec B) {
    Vec P(n);
    std::reverse(A.begin(), A.end());
    int n1 = A.size(), n2 = B.size(), n = extend(n1 + n2 - 1);

    Vec F = A, G = B;
    for (auto &x : F) x = 1LL * x * x % MOD * x % MOD;
    F.resize(n), G.resize(n), DFT(F), DFT(G);
    for (int i = 0; i < n; i++) F[i] = 1LL * F[i] * G[i] % MOD;
    P = P + F;
    
    F = A, G = B;
    for (auto &x : F) x = 1LL * x * x % MOD;
    for (auto &x : G) x = 1LL * x * x % MOD;
    F.resize(n), G.resize(n), DFT(F), DFT(G);
    for (int i = 0; i < n; i++) F[i] = 1LL * F[i] * G[i] % MOD;
    P = P - 2 * F;
    
    F = A, G = B;
    for (auto &x : G) x = 1LL * x * x % MOD * x % MOD;
    F.resize(n), G.resize(n), DFT(F), DFT(G);
    for (int i = 0; i < n; i++) F[i] = 1LL * F[i] * G[i] % MOD;
    P = P + F;

    IDFT(P), P.resize(n1 + n2 - 1);

    return P;
}
int main() {
    scanf("%d%d%s%s", &m, &n, s, t);
    Vec A(m), B(n);
    for (int i = 0; i < m; i++) A[i] = (s[i] == '*' ? 0 : s[i] - 'a' + 1);
    for (int i = 0; i < n; i++) B[i] = (t[i] == '*' ? 0 : t[i] - 'a' + 1);
    Vec F = solve(A, B), ans;
    for (int i = m - 1; i < n; i++) {
        if (F[i] == 0) ans.emplace_back(i - m + 2);
    }
    printf("%d\n", (int)ans.size());
    print(ans);
    return 0;
}