← 返回题目列表

Codeforces · 822/B

B. 填字游戏解决

中文机器翻译题面 查看原题

Erelong Leha 对计算两个阶乘的最大公约数感到无聊。因此他决定解决一些填字游戏。众所周知,这是一个非常有趣的职业,尽管有时会很困难。在解决一个填字游戏的过程中,莱哈必须解决一项简单的任务。你也能做到,不是吗?

Leha 有两个字符串 s 和 t。黑客想要以这样的方式更改字符串 s,以便可以在 t 中找到它作为子字符串。所有的改变应该如下:Leha 在字符串 s 中选择一个位置,并将该位置的符号替换为问号“?”。黑客确信比较中的问号可以起到任意符号的作用。例如,如果他得到字符串 s="ab?b" 作为结果,它将作为子字符串出现在 t="aabrbb" 中。

保证字符串 s 的长度不超过字符串 t 的长度。帮助黑客在s中替换尽可能少的符号,以便替换的结果可以作为子字符串在t中找到。符号“?”应被视为等于任何其他符号。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ m ≤ 1000) — 对应字符串 s 的长度和字符串 t 的长度。

第二行包含n个小写英文字母——字符串s。

第三行包含m个小写英文字母——字符串t。

输出

在第一行中打印单个整数 k — 需要替换的符号的最小数量。

在第二行中打印 k 个不同的整数,表示字符串 s 中需要替换的符号的位置。以任意顺序打印位置。如果有多个解决方案,请打印其中任何一个。位置编号从 1 开始。

示例

输入 #1

3 5
abc
xaybz

输出 #1

2
2 3

输入 #2

4 10
abcd
ebceabazcd

输出 #2

1
2