最新消息:380元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 字符串编码

C++ 少儿编程 1301浏览 0评论

友情提示:380元/半年,儿童学编程,就上码丁实验室

【题目描述】

小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
paraparallelogramgram
qolorreraglom

【输出样例2】

1
5

【数据规模】

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

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

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

您必须 登录 才能发表评论!