编程题

1692:字符串编码


时间限制: 1000 ms         内存限制: 262144 KB
提交数:349    通过数: 67

【题目描述】

小P最近又发明了一种新的字符串编码方法。

具体地,我们可以取若干对不相交的小写字母对(不相交指每个小写字母至多出现一次),然后对于一个由小写字母组成的字符串$T$,我们将$T$中出现在选中字母对中的字母替换为这个字母对中的另一个字母。

举个例子:我们选中了三对字母$(l,r),(p,q)$和$(a,o)$,那么,“$parallelogram$”这个字符串将被编码为“$qolorreraglom$”。

小P已经有了两个字符串$S$和$T$。他惊讶地发现,$S$的许多子串竟然可以通过他所发明的新编码方法编码得到$T$。于是小P想知道,$S$中有多少个子串可以用如上所描述字符串编码方法编码得到$T$。你能帮助他吗?

【输入】

第一行包含两个整数$n,m$,表示$S$与$T$的串长。

接下来两行两个由小写字母构成的字符串$S$与$T$。

【输出】

第一行一个整数,表示满足条件的子串的个数$k$。

接下来一行按照升序输出$k$个整数,表示每个子串开始的位置(下标从$1$开始)。

【输入样例】

11 5
abacabadaba
acaba

【输出样例】

3
1 3 7

【提示】

【输入样例2】

21 13\nparaparallelogramgram\nqolorreraglom

【输出样例2】

1\n5

【数据规模】

对于10%的数据,$n,m≤10$。

对于30%的数据,$m≤50$。

对于100%的数据,$n,m≤2×10^5$。

查看答案
赣ICP备20007335号-2