← 返回题目列表

Codeforces · 533/F

F. 编码

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

Polycarp 发明了一种新的字符串编码方法。假设我们有字符串 T,由小写英文字母组成。让我们选择几对英文字母,使得每个字母最多出现一对。然后,如果 T 中有一对字母,那么我们将 T 中的每个字母替换为其配对字母。例如,如果您选择对 (l, r)、(p, q) 和 (a, o),则单词“parallelogram”根据给定的编码原理将转换为单词“qolorreraglom”。

Polycarpus 已经有两个字符串 S 和 T。他怀疑字符串 T 是从字符串 S 的某个子字符串应用给定的编码方法后获得的。找到 S 中的所有位置 mi (1 ≤ mi ≤ |S| - |T| + 1),这样就可以从子字符串 SmiSmi + 1... Smi + |T| 获得 T。 - 1 通过使用一些英文字母对来应用所描述的编码操作

输入

输入的第一行包含两个整数,|S|和|T| (1 ≤ |T| ≤ |S| ≤ 2·105) — 分别是字符串 S 和字符串 T 的长度。

输入的第二行和第三行分别包含字符串 S 和 T。两个字符串均仅包含小写英文字母。

输出

打印数量 k — 字符串 S 中合适位置的数量。

在下一行中打印 k 个整数 m1, m2, ..., mk — 按升序排列的合适位置的编号。

示例

输入 #1

11 5
abacabadaba
acaba

输出 #1

3
1 3 7

输入 #2

21 13
paraparallelogramgram
qolorreraglom

输出 #2

1
5