G. Anthem of Berland

Codeforces

IDCF808G

Time3000ms

Memory256MB

Difficulty—

dpstrings

English · Original

Chinese · Translation

Formal · Original

Berland has a long and glorious history. To increase awareness about it among younger citizens, King of Berland decided to compose an anthem. Though there are lots and lots of victories in history of Berland, there is the one that stand out the most. King wants to mention it in the anthem as many times as possible. He has already composed major part of the anthem and now just needs to fill in some letters. King asked you to help him with this work. The anthem is the string _s_ of no more than 105 small Latin letters and question marks. The most glorious victory is the string _t_ of no more than 105 small Latin letters. You should replace all the question marks with small Latin letters in such a way that the number of occurrences of string _t_ in string _s_ is maximal. Note that the occurrences of string _t_ in _s_ can overlap. Check the third example for clarification. ## Input The first line contains string of small Latin letters and question marks _s_ (1 ≤ |_s_| ≤ 105). The second line contains string of small Latin letters _t_ (1 ≤ |_t_| ≤ 105). **Product of lengths of strings |_s_|·|_t_| won't exceed 107.** ## Output Output the maximum number of occurrences of string _t_ you can achieve by replacing all the question marks in string _s_ with small Latin letters. [samples] ## Note In the first example the resulting string _s_ is _"winlose**win**winl**win**w**in**"_ In the second example the resulting string _s_ is _"glo**r**yto**r**e**or**an**d**"_. The last letter of the string can be arbitrary. In the third example occurrences of string _t_ are overlapping. String _s_ with maximal number of occurrences of _t_ is _"**ab**c**abcab**"_.

Berland 拥有悠久而辉煌的历史。为了提高年轻公民对这段历史的认知，Berland 国王决定创作一首国歌。尽管 Berland 历史上有无数胜利，但其中有一场最为突出。国王希望在国歌中尽可能多地提及这场胜利。他已经完成了国歌的主要部分，现在只需填入一些字母。国王请你帮助他完成这项工作。国歌是一个由不超过 #cf_span[105] 个小写拉丁字母和问号组成的字符串 #cf_span[s]。最辉煌的胜利是一个由不超过 #cf_span[105] 个小写拉丁字母组成的字符串 #cf_span[t]。你需要将字符串 #cf_span[s] 中的所有问号替换为小写拉丁字母，使得字符串 #cf_span[t] 在字符串 #cf_span[s] 中的出现次数最大化。注意，字符串 #cf_span[t] 在 #cf_span[s] 中的出现可以重叠。请参见第三个示例以获得澄清。第一行包含由小写拉丁字母和问号组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 105]）。第二行包含由小写拉丁字母组成的字符串 #cf_span[t]（#cf_span[1 ≤ |t| ≤ 105]）。 *字符串长度的乘积 #cf_span[|s|·|t|] 不会超过 #cf_span[107]。* 请输出通过将字符串 #cf_span[s] 中的所有问号替换为小写拉丁字母，所能达到的字符串 #cf_span[t] 的最大出现次数。在第一个示例中，得到的字符串 #cf_span[s] 是 _"winlose*win*winl*win*w*in*"_。在第二个示例中，得到的字符串 #cf_span[s] 是 _"glo*r*yto*r*e*or*an*d*"_。字符串的最后一个字母可以是任意的。在第三个示例中，字符串 #cf_span[t] 的出现是重叠的。具有最多 #cf_span[t] 出现次数的字符串 #cf_span[s] 是 _"*ab*c*abcab*"_。 ## Input 第一行包含由小写拉丁字母和问号组成的字符串 #cf_span[s]（#cf_span[1 ≤ |s| ≤ 105]）。第二行包含由小写拉丁字母组成的字符串 #cf_span[t]（#cf_span[1 ≤ |t| ≤ 105]）。*字符串长度的乘积 #cf_span[|s|·|t|] 不会超过 #cf_span[107]。* ## Output 请输出通过将字符串 #cf_span[s] 中的所有问号替换为小写拉丁字母，所能达到的字符串 #cf_span[t] 的最大出现次数。 [samples] ## Note 在第一个示例中，得到的字符串 #cf_span[s] 是 _"winlose*win*winl*win*w*in*"_。在第二个示例中，得到的字符串 #cf_span[s] 是 _"glo*r*yto*r*e*or*an*d*"_。字符串的最后一个字母可以是任意的。在第三个示例中，字符串 #cf_span[t] 的出现是重叠的。具有最多 #cf_span[t] 出现次数的字符串 #cf_span[s] 是 _"*ab*c*abcab*"_。

**Definitions** Let $ s \in (\Sigma \cup \{?\})^* $ be the input string of length $ n $, where $ \Sigma $ is the set of lowercase Latin letters. Let $ t \in \Sigma^* $ be the target string of length $ m $. **Constraints** 1. $ 1 \leq n \leq 10^5 $, $ 1 \leq m \leq 10^5 $, and $ n \cdot m \leq 10^7 $. 2. Each character in $ s $ is either a lowercase Latin letter or a question mark `?`. 3. Each character in $ t $ is a lowercase Latin letter. **Objective** Replace every `?` in $ s $ with any character in $ \Sigma $ to maximize the number of occurrences of $ t $ as a substring in the resulting string. An occurrence of $ t $ at position $ i $ (0-indexed) is valid if $ s[i:i+m] = t $ (after replacement). Occurrences may overlap. Compute the **maximum possible number of non-overlapping or overlapping occurrences** of $ t $ in $ s $ after optimal replacement of all `?`.

Samples

Input #1

winlose???winl???w??
win

Output #1

Input #2

glo?yto?e??an?
or

Output #2

Input #3

??c?????
abcab

Output #3

API Response (JSON)

{
  "problem": {
    "name": "G. Anthem of Berland",
    "description": {
      "content": "Berland has a long and glorious history. To increase awareness about it among younger citizens, King of Berland decided to compose an anthem. Though there are lots and lots of victories in history of",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF808G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Berland has a long and glorious history. To increase awareness about it among younger citizens, King of Berland decided to compose an anthem.\n\nThough there are lots and lots of victories in history of...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Berland 拥有悠久而辉煌的历史。为了提高年轻公民对这段历史的认知，Berland 国王决定创作一首国歌。\n\n尽管 Berland 历史上有无数胜利，但其中有一场最为突出。国王希望在国歌中尽可能多地提及这场胜利。\n\n他已经完成了国歌的主要部分，现在只需填入一些字母。国王请你帮助他完成这项工作。\n\n国歌是一个由不超过 #cf_span[105] 个小写拉丁字母和问号组成的字符串 #cf_span...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in (\\Sigma \\cup \\{?\\})^* $ be the input string of length $ n $, where $ \\Sigma $ is the set of lowercase Latin letters.  \nLet $ t \\in \\Sigma^* $ be the target string of leng...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments