D. Suitable Replacement

Codeforces

IDCF825D

Time1000ms

Memory256MB

Difficulty—

binary searchgreedyimplementation

English · Original

Chinese · Translation

Formal · Original

You are given two strings _s_ and _t_ consisting of small Latin letters, string _s_ can also contain _'?'_ characters. _Suitability_ of string _s_ is calculated by following metric: Any two letters can be swapped positions, these operations can be performed arbitrary number of times over any pair of positions. Among all resulting strings _s_, you choose the one with the largest number of **non-intersecting** occurrences of string _t_. _Suitability_ is this number of occurrences. You should replace all _'?'_ characters with small Latin letters in such a way that the _suitability_ of string _s_ is maximal. ## Input The first line contains string _s_ (1 ≤ |_s_| ≤ 106). The second line contains string _t_ (1 ≤ |_t_| ≤ 106). ## Output Print string _s_ with _'?'_ replaced with small Latin letters in such a way that _suitability_ of that string is maximal. If there are multiple strings with maximal _suitability_ then print any of them. [samples] ## Note In the first example string _"baab"_ can be transformed to _"abab"_ with swaps, this one has _suitability_ of _2_. That means that string _"baab"_ also has _suitability_ of _2_. In the second example maximal _suitability_ you can achieve is _1_ and there are several dozens of such strings, _"azbz"_ is just one of them. In the third example there are no _'?'_ characters and the _suitability_ of the string is _0_.

你被给定两个由小写拉丁字母组成的字符串 #cf_span[s] 和 #cf_span[t]，字符串 #cf_span[s] 中也可能包含 _'?'_ 字符。字符串 #cf_span[s] 的 _适宜性_ 按如下方式计算：可以任意交换任意两个字符的位置，这种操作可以对任意位置对执行任意多次。在所有可能得到的字符串 #cf_span[s] 中，你选择具有最多 *不相交* 的子串 #cf_span[t] 出现次数的那个。_适宜性_ 即为这个出现次数。你需要将所有 _'?'_ 字符替换为小写拉丁字母，使得字符串 #cf_span[s] 的 _适宜性_ 最大化。第一行包含字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 106]）。第二行包含字符串 #cf_span[t]（#cf_span[1 ≤ |t| ≤ 106]）。请输出将 #cf_span[s] 中的 _'?'_ 替换为小写拉丁字母后的字符串，使得其 _适宜性_ 最大。如果有多个字符串具有最大 _适宜性_，输出其中任意一个即可。在第一个例子中，字符串 _"baab"_ 可以通过交换变换为 _"abab"_，后者具有 _适宜性_ 为 _2_。这意味着字符串 _"baab"_ 的 _适宜性_ 也为 _2_。在第二个例子中，你能达到的最大 _适宜性_ 为 _1_，有数十种这样的字符串，_"azbz"_ 只是其中之一。在第三个例子中，字符串中没有 _'?'_ 字符，其 _适宜性_ 为 _0_。 ## Input 第一行包含字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 106]）。第二行包含字符串 #cf_span[t]（#cf_span[1 ≤ |t| ≤ 106]）。 ## Output 请输出将 #cf_span[s] 中的 _'?'_ 替换为小写拉丁字母后的字符串，使得其 _适宜性_ 最大。如果有多个字符串具有最大 _适宜性_，输出其中任意一个即可。 [samples] ## Note 在第一个例子中，字符串 _"baab"_ 可以通过交换变换为 _"abab"_，后者具有 _适宜性_ 为 _2_。这意味着字符串 _"baab"_ 的 _适宜性_ 也为 _2_。在第二个例子中，你能达到的最大 _适宜性_ 为 _1_，有数十种这样的字符串，_"azbz"_ 只是其中之一。在第三个例子中，字符串中没有 _'?'_ 字符，其 _适宜性_ 为 _0_。

**Definitions** Let $ s \in (\Sigma \cup \{?\})^* $ be the input string, where $ \Sigma $ is the set of lowercase Latin letters. Let $ t \in \Sigma^* $ be the target string. Let $ n = |s| $, $ m = |t| $. A *swap* is any transposition of two characters in $ s $. A *non-intersecting occurrence* of $ t $ in $ s $ is a substring $ s[i:i+m-1] $ such that it equals $ t $ as a multiset (i.e., after arbitrary swaps, the multiset of characters matches that of $ t $), and no two such occurrences share a position. The *suitability* of $ s $ is the maximum number of non-overlapping (i.e., disjoint in indices) multisets of size $ m $ in $ s $, each having the same character frequencies as $ t $. **Constraints** 1. $ 1 \leq n \leq 10^6 $ 2. $ 1 \leq m \leq 10^6 $ 3. $ m \leq n $ 4. Each character in $ t $ is in $ \Sigma $. 5. Each character in $ s $ is either in $ \Sigma $ or is $ ? $. **Objective** Replace each $ ? $ in $ s $ with a character from $ \Sigma $ to maximize the number of non-intersecting occurrences of $ t $ (as multisets). Output any resulting string $ s' $ achieving this maximum suitability.

Samples

Input #1

?aa?
ab

Output #1

baab

Input #2

??b?
za

Output #2

azbz

Input #3

abcd
abacaba

Output #3

abcd

API Response (JSON)

{
  "problem": {
    "name": "D. Suitable Replacement",
    "description": {
      "content": "You are given two strings _s_ and _t_ consisting of small Latin letters, string _s_ can also contain _'?'_ characters. _Suitability_ of string _s_ is calculated by following metric: Any two letters ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF825D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two strings _s_ and _t_ consisting of small Latin letters, string _s_ can also contain _'?'_ characters.\n\n_Suitability_ of string _s_ is calculated by following metric:\n\nAny two letters ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你被给定两个由小写拉丁字母组成的字符串 #cf_span[s] 和 #cf_span[t]，字符串 #cf_span[s] 中也可能包含 _'?'_ 字符。\n\n字符串 #cf_span[s] 的 _适宜性_ 按如下方式计算：\n\n可以任意交换任意两个字符的位置，这种操作可以对任意位置对执行任意多次。在所有可能得到的字符串 #cf_span[s] 中，你选择具有最多 *不相交* 的子串 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in (\\Sigma \\cup \\{?\\})^* $ be the input string, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ t \\in \\Sigma^* $ be the target string.  \nLet $ n = |s| $, $ m...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments