CF954I Yet Another String Matching Problem

假设你有两个字符串 $s$ 和 $t$，它们的长度相等。你可以进行如下操作任意次：选择两个不同的字符 $c_{1}$ 和 $c_{2}$，然后将这两个字符串中所有的 $c_{1}$ 都替换成 $c_{2}$。我们定义字符串 $s$ 和 $t$ 之间的距离为使这两个字符串相等所需的最少操作次数。例如，如果 $s$ 是 abcd，$t$ 是 ddcb，那么它们之间的距离是 $2$——我们可以先将所有的 a 替换成 b，这样 $s$ 变成 bbcd，然后再将所有的 b 替换成 d，这样两个字符串都变成 ddcd。 现在给定两个字符串 $S$ 和 $T$。对于 $S$ 的每一个长度为 $|T|$ 的子串，你需要计算该子串与 $T$ 之间的距离。

第一行包含字符串 $S$，第二行包含字符串 $T$（$1 \leq |T| \leq |S| \leq 125000$）。两个字符串均由小写拉丁字母 a 到 f 组成。

输出 $|S| - |T| + 1$ 个整数。第 $i$ 个整数表示 $S$ 从第 $i$ 个位置开始，长度为 $|T|$ 的子串与字符串 $T$ 之间的距离。

由 ChatGPT 4.1 翻译