CF954I.Yet Another String Matching Problem

Suppose you have two strings s and t, and their length is equal. You may perform the following operation any number of times: choose two different characters _c_1 and _c_2, and replace every occurence of _c_1 in both strings with _c_2. Let's denote the distance between strings s and t as the minimum number of operations required to make these strings equal. For example, if s is abcd and t is ddcb, the distance between them is 2 — we may replace every occurence of a with b, so s becomes bbcd, and then we may replace every occurence of b with d, so both strings become ddcd.

You are given two strings S and T. For every substring of S consisting of |T| characters you have to determine the distance between this substring and T.

假设你有两个字符串 $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$ 之间的距离。

The first line contains the string S, and the second — the string T (1 ≤ |T| ≤ |S| ≤ 125000). Both strings consist of lowercase Latin letters from a to f.

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

Print |S| - |T| + 1 integers. The i-th of these integers must be equal to the distance between the substring of S beginning at i-th index with length |T| and the string T.

输出 $|S| - |T| + 1$ 个整数。其中第 $i$ 个整数必须等于字符串 $S$ 中从第 $i$ 个位置开始、长度为 $|T|$ 的子串与字符串 $T$ 之间的距离。