I. Yet Another String Matching Problem

Codeforces

IDCF954I

Time4000ms

Memory256MB

Difficulty—

fftmath

English · Original

Chinese · Translation

Formal · Original

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_. ## Input 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_. ## Output 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_. [samples]

假设你有两个字符串 #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_。给定两个字符串 #cf_span[S] 和 #cf_span[T]。对于 #cf_span[S] 中每一个由 #cf_span[|T|] 个字符组成的子串，你需要确定该子串与 #cf_span[T] 之间的 _距离_。第一行包含字符串 #cf_span[S]，第二行包含字符串 #cf_span[T]（#cf_span[1 ≤ |T| ≤ |S| ≤ 125000]）。两个字符串均由小写拉丁字母 _a_ 到 _f_ 组成。请输出 #cf_span[|S| - |T| + 1] 个整数。第 #cf_span[i] 个整数必须等于从 #cf_span[S] 的第 #cf_span[i] 个字符开始、长度为 #cf_span[|T|] 的子串与字符串 #cf_span[T] 之间的 _距离_。 ## Input 第一行包含字符串 #cf_span[S]，第二行包含字符串 #cf_span[T]（#cf_span[1 ≤ |T| ≤ |S| ≤ 125000]）。两个字符串均由小写拉丁字母 _a_ 到 _f_ 组成。 ## Output 请输出 #cf_span[|S| - |T| + 1] 个整数。第 #cf_span[i] 个整数必须等于从 #cf_span[S] 的第 #cf_span[i] 个字符开始、长度为 #cf_span[|T|] 的子串与字符串 #cf_span[T] 之间的 _距离_。 [samples]

**Definitions** Let $ S, T \in \{a,b,c,d,e,f\}^* $ be two strings with $ |T| \leq |S| $. For 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| $. **Operation** A 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. **Distance Definition** The distance $ d(S_i, T) $ is the minimum number of such operations required to make $ S_i = T $. **Constraints** 1. $ 1 \leq |T| \leq |S| \leq 125000 $ 2. All characters in $ S $ and $ T $ are from the alphabet $ \{a,b,c,d,e,f\} $ **Objective** For each $ i \in \{0, 1, \dots, |S| - |T|\} $, compute $ d(S_i, T) $. Output $ |S| - |T| + 1 $ integers: $ d(S_0, T), d(S_1, T), \dots, d(S_{|S|-|T|}, T) $.

Samples

Input #1

abcdefa
ddcb

Output #1

2 3 3 3

API Response (JSON)

{
  "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 occur...",
      "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] 之间的 _距离_ 为使这两个字符串相等所需的最少操作次数。例如...",
      "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 $ starti...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments