B. 小雅米的开门炮

传统 1000 ms 256 MiB
标准 IO
文本比较

题目描述

众所周知,小雅米有一个神奇的开门炮,并且经常用它来欺负丢丢陈。有一天,丢丢陈带回了它两个心仪的字符串 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