CF954I Yet Another String Matching Problem

传送门

每次操作可以把两个字符串中所有同一种字符变成另外一种
定义两个长度相等的字符串之间的距离为：使两个字符串相等所需要操作的次数的最小值
求 \(s\) 中每一个长度为 \(|t|\) 的连续子串与 \(t\) 的距离
字符集为小写字母 \('a'\) 到 \('f'\)

Sol

考虑如何计算两个等长串的距离
相当于两个匹配的字符之间连边，同一个连通块内可以互相转化，答案就是并查集合并的次数
本题的字符集大小只有 \(6\)，那么考虑枚举两种字符匹配连边
匹配就是一个非常套路的反转 \(+\) \(FFT\) 了

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn(1 << 18);
const double pi(acos(-1));

struct Complex {
    double a, b;

    inline Complex() {
        a = b = 0;
    }

    inline Complex(double _a, double _b) {
        a = _a, b = _b;
    }

    inline Complex operator +(Complex x) const {
        return Complex(a + x.a, b + x.b);
    }

    inline Complex operator -(Complex x) const {
        return Complex(a - x.a, b - x.b);
    }

    inline Complex operator *(Complex x) const {
        return Complex(a * x.a - b * x.b, a * x.b + b * x.a);
    }

    inline Complex Conj() {
        return Complex(a, -b);
    }
};

Complex a[maxn], b[maxn], w[maxn];
int r[maxn], l, deg, g[maxn], h[maxn], cnt[maxn];

inline void FFT(Complex *p, int opt) {
    register int i, j, k, t;
    register Complex wn, x, y;
    for (i = 0; i < deg; ++i) if (r[i] < i) swap(p[r[i]], p[i]);
    for (i = 1; i < deg; i <<= 1)
        for(t = i << 1, j = 0; j < deg; j += t)
            for (k = 0; k < i; ++k) {
                wn = w[deg / i * k];
                if (opt == -1) wn.b *= -1;
                x = p[j + k], y = wn * p[i + j + k];
                p[j + k] = x + y, p[i + j + k] = x - y;
            }
}

inline void Init(int n) {
    register int i;
    for (deg = 1, l = 0; deg < n; deg <<= 1) ++l;
    for (i = 0; i < deg; ++i) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    for (i = 0; i < deg; ++i) w[i] = Complex(cos(pi * i / deg), sin(pi * i / deg));
}

inline void Mul(int *p, int *q, int *f) {
    register int i, k;
    register Complex ca, da, db;
    for (i = 0; i < deg; ++i) a[i] = Complex(p[i], q[i]);
    for (FFT(a, 1), i = 0; i < deg; ++i) {
        k = (deg - i) & (deg - 1), ca = a[k].Conj();
        b[i] = (ca + a[i]) * (a[i] - ca) * Complex(0, -0.25);
    }
    for (FFT(b, -1), i = 0; i < deg; ++i) f[i] = (int)(b[i].a / deg + 0.5);
}

int n, m, mp[7][7][maxn], fa[7], ans;
char s[maxn], t[maxn];

inline int Find(int x) {
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}

int main() {
    register int i, j, k, d;
    scanf(" %s %s", s + 1, t + 1), n = strlen(s + 1), m = strlen(t + 1);
    reverse(t + 1, t + m + 1), Init(n + m + 1), d = n - m + 1;
    for (i = 1; i <= 6; ++i)
        for (j = 1; j <= 6; ++j)
            if (i != j) {
                for (k = 1; k <= n; ++k) g[k] = s[k] - 'a' + 1 == i;
                for (k = 1; k <= m; ++k) h[k] = t[k] - 'a' + 1 == j;
                for (Mul(g, h, cnt), k = 1; k <= d; ++k) mp[i][j][k] = cnt[m + k] > 0;
            }
    for (i = 1; i <= d; ++i) {
        for (ans = 0, j = 1; j <= 6; ++j) fa[j] = j;
        for (j = 1; j <= 6; ++j)
            for (k = 1; k <= 6; ++k)
                if (mp[j][k][i] && (Find(j) ^ Find(k))) ++ans, fa[Find(j)] = Find(k);
        printf("%d ", ans);
    }
    return 0;
}