{"problem":{"name":"I. Yet Another String Matching Problem","description":{"content":"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 occur","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF954I"},"statements":[{"statement_type":"Markdown","content":"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_.\n\nYou 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_.\n\n## Input\n\nThe 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_.\n\n## Output\n\nPrint |_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_.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"假设你有两个字符串 #cf_span[s] 和 #cf_span[t]，它们长度相等。你可以任意次执行以下操作：选择两个不同的字符 #cf_span[c1] 和 #cf_span[c2]，并将两个字符串中所有 #cf_span[c1] 替换为 #cf_span[c2]。我们定义字符串 #cf_span[s] 和 #cf_span[t] 之间的 _距离_ 为使这两个字符串相等所需的最少操作次数。例如，若 #cf_span[s] 为 _abcd_ 而 #cf_span[t] 为 _ddcb_，则它们之间的 _距离_ 为 #cf_span[2] —— 我们可以将所有 _a_ 替换为 _b_，使得 #cf_span[s] 变为 _bbcd_，然后将所有 _b_ 替换为 _d_，使得两个字符串都变为 _ddcd_。\n\n给定两个字符串 #cf_span[S] 和 #cf_span[T]。对于 #cf_span[S] 中每一个由 #cf_span[|T|] 个字符组成的子串，你需要确定该子串与 #cf_span[T] 之间的 _距离_。\n\n第一行包含字符串 #cf_span[S]，第二行包含字符串 #cf_span[T]（#cf_span[1 ≤ |T| ≤ |S| ≤ 125000]）。两个字符串均由小写拉丁字母 _a_ 到 _f_ 组成。\n\n请输出 #cf_span[|S| - |T| + 1] 个整数。第 #cf_span[i] 个整数必须等于从 #cf_span[S] 的第 #cf_span[i] 个字符开始、长度为 #cf_span[|T|] 的子串与字符串 #cf_span[T] 之间的 _距离_。\n\n## Input\n\n第一行包含字符串 #cf_span[S]，第二行包含字符串 #cf_span[T]（#cf_span[1 ≤ |T| ≤ |S| ≤ 125000]）。两个字符串均由小写拉丁字母 _a_ 到 _f_ 组成。\n\n## Output\n\n请输出 #cf_span[|S| - |T| + 1] 个整数。第 #cf_span[i] 个整数必须等于从 #cf_span[S] 的第 #cf_span[i] 个字符开始、长度为 #cf_span[|T|] 的子串与字符串 #cf_span[T] 之间的 _距离_。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ S, T \\in \\{a,b,c,d,e,f\\}^* $ be two strings with $ |T| \\leq |S| $.  \nFor each $ i \\in \\{0, 1, \\dots, |S| - |T|\\} $, define $ S_i = S[i:i+|T|] $ as the substring of $ S $ starting at index $ i $ of length $ |T| $.\n\n**Operation**  \nA valid operation: choose two distinct characters $ c_1 \\ne c_2 $, and replace all occurrences of $ c_1 $ with $ c_2 $ in **both** strings simultaneously.\n\n**Distance Definition**  \nThe distance $ d(S_i, T) $ is the minimum number of such operations required to make $ S_i = T $.\n\n**Constraints**  \n1. $ 1 \\leq |T| \\leq |S| \\leq 125000 $  \n2. All characters in $ S $ and $ T $ are from the alphabet $ \\{a,b,c,d,e,f\\} $\n\n**Objective**  \nFor each $ i \\in \\{0, 1, \\dots, |S| - |T|\\} $, compute $ d(S_i, T) $.  \nOutput $ |S| - |T| + 1 $ integers: $ d(S_0, T), d(S_1, T), \\dots, d(S_{|S|-|T|}, T) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF954I","tags":["fft","math"],"sample_group":[["abcdefa\nddcb","2 3 3 3"]],"created_at":"2026-03-03 11:00:39"}}