题目链接 Educational Codeforces Round 40 Problem I
题意 定义两个长度相等的字符串之间的距离为：
把两个字符串中所有同一种字符变成另外一种，使得两个字符串相等所需要操作的次数的最小值。
求$s$中每一个长度为$t$的长度的连续子串与$t$的距离。字符集为小写字母$a$到$f$
首先解决求两个长度相等的字符串之间的距离这个问题。
$s$和$t$相同位上的字母连一条无向边，最后的答案是$s$和$t$中所有出现过的字符的个数减去这个无向图的连通块个数。
现在考虑$s$的所有子串和$t$匹配的问题。
令$s$的长度为$n$，$t$的长度为$m$
那么s的符合题意的子串一共有$n - m + 1$个。
把这$n - m + 1$个子串看成$n - m + 1$个独立的无向图，每个无向图是独立的；
现在我们两两枚举边（一共$30$条边），我们要做的就是快速求出这$n - m + 1$个无向图中，
有哪些是有这条边的。
这个时候我们把s和t转成一个$01$序列，设为$a$和$b$
在$a$和$b$中，若$a_{i} = b_{j} = 1$， 那么$c_{i-j} = 1$。
我们可以把$b$数组反转之后用FFT加速求出$c$。
那么在那些值为$1$的下标对应的无向图中就一定有这条边，并查集处理一下就好了。
时间复杂度$O(30nlogn)$
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define fi first
#define se second
const double PI = acos(-1.0);
const int N = 125010;
struct dsu{
int father[10];
void init(){
rep(i, 0, 7) father[i] = i;
}
int getfather(int x){
return father[x] == x ? x : father[x] = getfather(father[x]);
}
} c[N];
char s[N], t[N];
int a[N << 1], b[N << 1];
int n, m;
int ans[N];
struct Complex{
double x, y;
Complex(double x = 0.0, double y = 0.0) : x(x), y(y){}
Complex operator + (const Complex &b) const{
return Complex(x + b.x, y + b.y);
}
Complex operator - (const Complex &b) const{
return Complex(x - b.x, y - b.y);
}
Complex operator * (const Complex &b) const{
return Complex(x * b.x - y * b.y, x * b.y + y * b.x);
}
};
Complex x1[N << 2], x2[N << 2];
void change(Complex y[], int len){
for (int i = 1, j = len / 2; i < len - 1; i++){
if (i < j) swap(y[i], y[j]);
int k = len / 2;
while (j >= k){
j -= k;
k /= 2;
}
if (j < k) j += k;
}
}
void fft(Complex y[], int len, int on){
change(y, len);
for (int h = 2; h <= len; h <<= 1){
Complex wn(cos(-on * 2 * PI / h), sin(-on * 2 * PI / h));
for (int j = 0; j < len; j += h){
Complex w(1, 0);
for (int k = j; k < j + h / 2; k++){
Complex u = y[k];
Complex t = w * y[k + h / 2];
y[k] = u + t;
y[k + h / 2] = u - t;
w = w * wn;
}
}
}
if (on == -1){
rep(i, 0, len - 1) y[i].x /= len;
}
}
void mul(int p[], int dp, int q[], int dq){
int len = 1;
while (len <= dp + dq) len <<= 1;
rep(i, 0, dp)
x1[i] = Complex(p[i], 0);
rep(i, dp + 1, len - 1)
x1[i] = Complex(0, 0);
rep(i, 0, dq)
x2[i] = Complex(q[i], 0);
rep(i, dq + 1, len - 1)
x2[i] = Complex(0, 0);
fft(x1, len, 1);
fft(x2, len, 1);
rep(i, 0, len - 1)
x1[i] = x1[i] * x2[i];
fft(x1, len, -1);
rep(i, 0, dp + dq)
p[i] = (int)(x1[i].x + 0.5);
rep(i, 0, dp + dq)
if (p[i] > 0) p[i] = 1;
dp += dq;
}
void work(int pos, int x, int y){
int fx = c[pos].getfather(x), fy = c[pos].getfather(y);
if (fx == fy) return;
assert(pos >= 1 && pos <= n - m + 1);
++ans[pos];
c[pos].father[fx] = fy;
}
int main(){
scanf("%s%s", s, t);
n = strlen(s), m = strlen(t);
rep(i, 1, n - m + 1) c[i].init();
rep(i, 0, 5){
rep(j, 0, 5){
if (i == j) continue;
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
rep(k, 0, n - 1) a[k] = (s[k] - 'a' == i);
rep(k, 0, m - 1) b[k] = (t[k] - 'a' == j);
reverse(b, b + m);
mul(a, n, b, m);
for (int k = m - 1, cnt = 1; cnt <= n - m + 1; ++k, ++cnt){
if (a[k]){
work(cnt, i + 1, j + 1);
}
}
}
}
rep(i, 1, n - m + 1) printf("%d\n", ans[i]);
return 0;
}