考虑到这个答案怎么算。
能发现相当于是对应的字符间相连边，那么一个连通块中的字符就要变成同一个字符。
于是一个连通块的代价就是 \(sz - 1\)。
所以令有 \(x\) 个连通块，最后的代价就是 \(|\Sigma| - x\)。
考虑到因为 \(|\Sigma| = 6\)，而 \(B_6 = 203\)（贝尔数，\(B_n\) 意义为大小为 \(n\) 的划分的数量）。
那么就可以考虑暴力枚举每种划分，也就是每种连通块的情况。
那么如果知道了连通块的情况，那么就可以把连通块里的所有字符都变为一个相同的字符。
那么令变换完的字符串为 \(S', T'\)。
那么只要 \(S'_{l\sim r}\) 与 \(T'\) 能匹配上，\(S_{l\sim r}\) 的答案可能对应的就是当前划分的情况，当然也有可能能让划分的集合更少，所以需要取个 \(\min\)。
对于匹配的部分用个 \(\text{KMP}\) 即可。
时间复杂度 \(O(B_{|\Sigma|}(|S| + |T|))\)。
代码
#include<bits/stdc++.h>
const int maxn = 2e5 + 10;
int n, m;
char S_[maxn], T_[maxn];
int S[maxn], T[maxn], s[maxn], t[maxn];
int to[6];
int nxt[maxn];
int ans[maxn];
inline void solve(int val) {
for (int i = 1; i <= n; i++)
s[i] = to[S[i]];
for (int i = 1; i <= n; i++)
t[i] = to[T[i]];
for (int i = 2, j = 0; i <= n; i++) {
while (j && t[j + 1] != t[i]) j = nxt[j];
j += t[j + 1] == t[i];
nxt[i] = j;
}
for (int i = 1, j = 0; i <= n; i++) {
while (j && t[j + 1] != s[i]) j = nxt[j];
j += t[j + 1] == s[i];
if (j == m) {
ans[i] = std::min(ans[i], val);
j = nxt[j];
}
}
}
void dfs(int w, std::vector<int> f) {
if (w == 6) {
solve(6 - f.size());
return ;
}
for (int p : f)
to[w] = p, dfs(w + 1, f);
to[w] = w, f.push_back(w), dfs(w + 1, f);
}
int main() {
scanf("%s%s", S_ + 1, T_ + 1);
n = strlen(S_ + 1), m = strlen(T_ + 1);
for (int i = 1; i <= n; i++)
S[i] = S_[i] - 'a';
for (int i = 1; i <= m; i++)
T[i] = T_[i] - 'a';
for (int i = m; i <= n; i++)
ans[i] = 1e9;
dfs(0, {});
for (int i = m; i <= n; i++)
printf("%d ", ans[i]);
return 0;
}