Visits: 150

P4173 残缺的字符串

带通配符的字符串匹配模板题。

两个长度为 $n$ 的字符串 $a, b$ 相等当且仅当 $\sum_{i=1}^n (a_i-b_i)^2 = 0$。

如果带有通配符，将通配符看成 $0$，则 $a,b$ 相等当且仅当 $\sum_{i=1}^n (a_i-b_i)^2a_ib_i = 0$。

套路地将 $a$ 串翻转，则 $a,b$ 相等当且仅当：
$$
\begin{aligned}
\sum_{i=1}^n (a_i-b_{n+1-i})^2a_ib_{n+1-i} &= 0 \\
\sum_{i=1}^n (a_i^2-2a_ib_{n+1-i}+b_{n+1-i}^2)a_ib_{n+1-i} &= 0 \\
\sum_{i=1}^n a_i^3b_{n+1-i} – \sum_{i=1}^n 2a_i^2b_{n+1-i}^2 + \sum_{i=1}^n a_ib_{n+1-i}^3 &= 0 \\
\end{aligned}
$$
最后即为三个卷积，可以 $\mathcal O(n \log n)$ 判断。

回到本题，首先翻转 $a$ 串，设 $f(p) = \sum_{i=1}^n a_i^3b_{n+p-i} – \sum_{i=1}^n 2a_i^2b_{n+p-i}^2 + \sum_{i=1}^n a_ib_{n+p-i}^3$。

则 $f(p) = 0$ 的 $p$ 即为合法的位置。

个人喜欢用 NTT，因为没有精度问题。当然会有冲突，但相当于 Hash，除了 CF 一般不会被卡。

namespace NTT {
    const int N = 1 << 21 | 1;
    int n, m, k, l, r[N];
    modint vk, g = 3, vg = 332748118, a[N], b[N];
    inline void ntt(modint *a, int n, int x) {
        for (int i = 0; i < n; i++) if (i < r[i]) swap(a[i], a[r[i]]);
        for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1) {
            modint W = (x > 0 ? g : vg) ^ ((P - 1) / o);
            for (int i = 0; i < n; i += o) {
                modint w = 1;
                for (int j = 0; j < k; j++, w *= W)
                    a[i+j+k] *= w,
                    a[i+j] += a[i+j+k],
                    a[i+j+k] = a[i+j] - a[i+j+k] - a[i+j+k];
            }
        }
    }
    inline void solve() {
        k = 1, l = 0;
        while (k <= n + m) k <<= 1, ++l;
        vk = (modint)1 / k;
        for (int i = 0; i < k; i++)
            r[i] = (r[i>>1] >> 1) | ((i & 1) << (l - 1));
        for (int i = n + 1; i < k; i++) a[i] = 0;
        for (int i = m + 1; i < k; i++) b[i] = 0;
        ntt(a, k, 1), ntt(b, k, 1);
        for (int i = 0; i < k; i++) a[i] *= b[i];
        ntt(a, k, -1);
        for (int i = 0; i <= n + m; i++) a[i] *= vk;
    }
}

const int N = 3e5 + 7;
int n, m;
char a[N], b[N];
modint f[N];

int main() {
    rd(n, m), rds(a, n), rds(b, m);
    reverse(a + 1, a + n + 1);
    NTT::n = n, NTT::m = m;
    for (int i = 1; i <= n; i++)
        if (a[i] == '*') a[i] = 0;
    for (int i = 1; i <= m; i++)
        if (b[i] == '*') b[i] = 0;

    for (int i = 1; i <= n; i++)
        NTT::a[i] = a[i] * a[i] * a[i];
    for (int i = 1; i <= m; i++)
        NTT::b[i] = b[i];
    NTT::solve();
    for (int p = 1; p + n - 1 <= m; p++)
        f[p] += NTT::a[p+n];

    for (int i = 1; i <= n; i++)
        NTT::a[i] = a[i] * a[i];
    for (int i = 1; i <= m; i++)
        NTT::b[i] = b[i] * b[i];
    NTT::solve();
    for (int p = 1; p + n - 1 <= m; p++)
        f[p] -= 2 * NTT::a[p+n];

    for (int i = 1; i <= n; i++)
        NTT::a[i] = a[i];
    for (int i = 1; i <= m; i++)
        NTT::b[i] = b[i] * b[i] * b[i];
    NTT::solve();
    for (int p = 1; p + n - 1 <= m; p++)
        f[p] += NTT::a[p+n];

    vi ans;
    for (int p = 1; p + n - 1 <= m; p++)
        if (!f[p]) ans.pb(p);
    print(ans.size());
    for (int x : ans) print(x, ' ');
    return 0;
}