Encoding

题面翻译

题目描述

坡旅甲发明了一种新的字符串编码方法．
具体来说，我们可以取若干对不相交的小写字母对(每个小写字母至多出现一次),然后对于一个由小写字母组成的字符串 $T$ ，我们将 $T$ 中出现在选中字母对中的字母替换为这个字母对中的另一个字母．

举个例子：我们选中了三对字母 $(l,r)$ , $(p,q)$ 和 $(a,o)$ ，那么，"parallelogram" 将会变为 "qolorreraglom"

现在，坡旅甲已经有了两个字符串 $S$ 和 $T$ ．他惊讶地发现，$S$ 的许多子串竟然可以通过他所发明的新编码方法得到 $T$．于是坡旅甲想知道，$S$ 中有多少个子串可以用如上所描述的字符串编码方法编码得到 $T$

输入格式

第一行包含两个整数 $n,m$ ，表示 $S$ 和 $T$ 的串长．
接下来两行由两个小写字母字符串 $S$ 和 $T$

输出格式

第一行一个整数，表示满足条件的子串个数 $k$
接下来一行按照升序输出 $k$ 个整数，表示每个子串开始的位置（下标从1开始）

数据范围

$n,m\le2\times10^5$

题目描述

Polycarp invented a new way to encode strings. Let's assume that we have string $T$ , consisting of lowercase English letters. Let's choose several pairs of letters of the English alphabet in such a way that each letter occurs in at most one pair. Then let's replace each letter in $T$ with its pair letter if there is a pair letter for it. For example, if you chose pairs (l, r), (p, q) and (a, o), then word "parallelogram" according to the given encoding principle transforms to word "qolorreraglom".

Polycarpus already has two strings, $S$ and $T$ . He suspects that string $T$ was obtained after applying the given encoding method from some substring of string $S$ . Find all positions $m_{i}$ in $S$ ( $1<=m_{i}<=|S|-|T|+1$ ), such that $T$ can be obtained fro substring $S_{mi}S_{mi}+1...\ S_{mi}+|T|-1$ by applying the described encoding operation by using some set of pairs of English alphabet letters

输入格式

The first line of the input contains two integers, $|S|$ and $|T|$ ( $1<=|T|<=|S|<=2·10^{5}$ ) — the lengths of string $S$ and string $T$ , respectively.

The second and third line of the input contain strings $S$ and $T$ , respectively. Both strings consist only of lowercase English letters.

输出格式

Print number $k$ — the number of suitable positions in string $S$ .

In the next line print $k$ integers $m_{1},m_{2},...,m_{k}$ — the numbers of the suitable positions in the increasing order.

样例 #1

样例输入 #1

11 5
abacabadaba
acaba

样例输出 #1

3
1 3 7

样例 #2

样例输入 #2

21 13
paraparallelogramgram
qolorreraglom

样例输出 #2

1
5