Yet Another String Matching Problem

题意翻译

- 给定字符串 $S,T$。 - 定义两个字符串的“距离”为：将这两个字符串中所有某种字符视作另一种字符，使得这两个字符串相等的最少次数。 - 试对于 $S$ 的每一个长度为 $|T|$ 的子串，求出它和 $T$ 的“距离”。 - $1\leq |S|,|T|\leq 125000$，所有字符 $\in\{a,b,c,d,e,f\}$。

题目描述

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 $ .

输入输出格式

输入格式

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.

输出格式

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 $ .

输入输出样例

输入样例 #1

abcdefa
ddcb

输出样例 #1

2 3 3 3 

题意翻译

- 给定字符串 $S,T$。 - 定义两个字符串的“距离”为：将这两个字符串中所有某种字符视作另一种字符，使得这两个字符串相等的最少次数。 - 试对于 $S$ 的每一个长度为 $|T|$ 的子串，求出它和 $T$ 的“距离”。 - $1\leq |S|,|T|\leq 125000$，所有字符 $\in\{a,b,c,d,e,f\}$。