B. Crossword solving

Codeforces

IDCF822B

Time1000ms

Memory256MB

Difficulty—

brute forceimplementationstrings

English · Original

Chinese · Translation

Formal · Original

Erelong Leha was bored by calculating of the greatest common divisor of two factorials. Therefore he decided to solve some crosswords. It's well known that it is a very interesting occupation though it can be very difficult from time to time. In the course of solving one of the crosswords, Leha had to solve a simple task. You are able to do it too, aren't you? Leha has two strings _s_ and _t_. The hacker wants to change the string _s_ at such way, that it can be found in _t_ as a substring. All the changes should be the following: Leha chooses one position in the string _s_ and replaces the symbol in this position with the question mark "_?_". The hacker is sure that the question mark in comparison can play the role of an arbitrary symbol. For example, if he gets string _s_\="_ab?b_" as a result, it will appear in _t_\="_aabrbb_" as a substring. Guaranteed that the length of the string _s_ doesn't exceed the length of the string _t_. Help the hacker to replace in _s_ as few symbols as possible so that the result of the replacements can be found in _t_ as a substring. The symbol "_?_" should be considered equal to any other symbol. ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ _m_ ≤ 1000) — the length of the string _s_ and the length of the string _t_ correspondingly. The second line contains _n_ lowercase English letters — string _s_. The third line contains _m_ lowercase English letters — string _t_. ## Output In the first line print single integer _k_ — the minimal number of symbols that need to be replaced. In the second line print _k_ **distinct** integers denoting the positions of symbols in the string _s_ which need to be replaced. Print the positions in any order. If there are several solutions print any of them. The numbering of the positions begins from one. [samples]

[{"iden":"statement","content":"不久后，Leha 对计算两个阶乘的最大公约数感到厌倦，因此他决定做一些填字游戏。众所周知，这是一项非常有趣的活动，尽管有时会非常困难。在解决其中一个填字游戏时，Leha 需要解决一个简单的问题。你也能做到，对吧？\n\nLeha 有两个字符串 #cf_span[s] 和 #cf_span[t]。黑客希望修改字符串 #cf_span[s]，使得修改后的结果能在 #cf_span[t] 中作为子串出现。所有的修改必须遵循以下规则：Leha 选择字符串 #cf_span[s] 中的一个位置，并将该位置的字符替换为问号 \"_?_\"。黑客确信，在比较时，问号可以代表任意字符。例如，如果他得到字符串 #cf_span[s]=\"_ab?b_\"，那么它将作为子串出现在 #cf_span[t]=\"_aabrbb_\" 中。\n\n保证字符串 #cf_span[s] 的长度不超过字符串 #cf_span[t] 的长度。请帮助黑客在 #cf_span[s] 中尽可能少地替换字符，使得替换后的结果能在 #cf_span[t] 中作为子串出现。符号 \"_?_\" 被认为等于任意其他字符。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ m ≤ 1000]) —— 分别表示字符串 #cf_span[s] 和 #cf_span[t] 的长度。\n\n第二行包含 #cf_span[n] 个小写英文字母 —— 字符串 #cf_span[s]。\n\n第三行包含 #cf_span[m] 个小写英文字母 —— 字符串 #cf_span[t]。\n\n第一行输出一个整数 #cf_span[k] —— 需要被替换的最少字符数。\n\n第二行输出 #cf_span[k] 个互不相同的整数，表示字符串 #cf_span[s] 中需要被替换的字符的位置。位置可以按任意顺序输出。如果有多个解，输出任意一个即可。位置编号从一开始。"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ m ≤ 1000]) —— 分别表示字符串 #cf_span[s] 和 #cf_span[t] 的长度。第二行包含 #cf_span[n] 个小写英文字母 —— 字符串 #cf_span[s]。第三行包含 #cf_span[m] 个小写英文字母 —— 字符串 #cf_span[t]。"},{"iden":"output","content":"第一行输出一个整数 #cf_span[k] —— 需要被替换的最少字符数。第二行输出 #cf_span[k] 个互不相同的整数，表示字符串 #cf_span[s] 中需要被替换的字符的位置。位置可以按任意顺序输出。如果有多个解，输出任意一个即可。位置编号从一开始。"},{"iden":"examples","content":"输入\n3 5\nabc\nxaybz\n输出\n2\n2 3 \n\n输入\n4 10\nabcd\neceabazcd\n输出\n1\n2 "}]"

**Definitions** Let $ n, m \in \mathbb{Z} $ with $ 1 \leq n \leq m \leq 1000 $. Let $ s = s_1 s_2 \dots s_n $ and $ t = t_1 t_2 \dots t_m $ be strings over the alphabet of lowercase English letters. **Constraints** - $ s $ has length $ n $, $ t $ has length $ m $. - A position $ i \in \{1, \dots, n\} $ may be replaced by "?" (wildcard), which matches any character. **Objective** Find the minimal number $ k $ of positions to replace with "?" in $ s $, such that for some starting index $ j \in \{1, \dots, m - n + 1\} $, $$ \forall i \in \{1, \dots, n\}, \quad \text{if } i \text{ is not replaced, then } s_i = t_{j+i-1}; \quad \text{otherwise, no constraint}. $$ Output $ k $ and a set of $ k $ distinct positions (1-indexed) in $ s $ to replace.

Samples

Input #1

3 5
abc
xaybz

Output #1

2
2 3

Input #2

4 10
abcd
ebceabazcd

Output #2

1
2

API Response (JSON)

{
  "problem": {
    "name": "B. Crossword solving",
    "description": {
      "content": "Erelong Leha was bored by calculating of the greatest common divisor of two factorials. Therefore he decided to solve some crosswords. It's well known that it is a very interesting occupation though i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF822B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Erelong Leha was bored by calculating of the greatest common divisor of two factorials. Therefore he decided to solve some crosswords. It's well known that it is a very interesting occupation though i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"不久后，Leha 对计算两个阶乘的最大公约数感到厌倦，因此他决定做一些填字游戏。众所周知，这是一项非常有趣的活动，尽管有时会非常困难。在解决其中一个填字游戏时，Leha 需要解决一个简单的问题。你也能做到，对吧？\\n\\nLeha 有两个字符串 #cf_span[s] 和 #cf_span[t]。黑客希望修改字符串 #cf_span[s...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq m \\leq 1000 $.  \nLet $ s = s_1 s_2 \\dots s_n $ and $ t = t_1 t_2 \\dots t_m $ be strings over the alphabet of lowercase English letter...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments