seuOJ222 - 小雅米的开门炮

题目描述

众所周知,小雅米有一个神奇的开门炮,并且经常用它来欺负丢丢陈。有一天,丢丢陈带回了它两个心仪的字符串 S,TS,T。小雅米趁丢丢陈不注意,用它的开门炮选择了两种字符 a,ba,ba,ba,b可以相同),使S中所有 aa 字符变为了 bb 字符,同时 bb 字符变为了 aa 字符。丢丢陈回来发现 SS 串不是原来的样子了,于是大哭起来。他开始拿着 TT 与所有可能的原本的 SS 进行比对。聪明的你能告诉丢丢陈,在所有的可能中,SS 串中哪些位置作为匹配的起始点,最终可能匹配成功(匹配成功意味着从 SS 串的某一点开始的连续一段长为 mm 的子串与 TT 串相同)。

输入格式

第一行输入两个整数 n,m(1n,m2×105)n,m(1\leq n, m\leq 2\times 10^5)。表示 SS 串与 TT 串的长度

第二行输入一个长度为 nn 的字符串,表示被开门炮轰击过的 SS 串。

第三行输入一个长度为 mm 的字符串,表示 TT 串。

输出格式

第一行输出一个整数 kk,表示可能匹配起点的个数。

第二行输出 kk 个数字,表示可能匹配起点的位置。

样例

样例输入

11 5
abacabadaba
acaba

样例输出

3
1 3 7