最简化题目描述

给出两个极长的字符串str1与str2，在str1中寻找所有出现的str2，并输出其起始位置。

算法指导

本题意欲开发模式串匹配程序。将待统计文段str1称作主串，特定组合字符串str2称作子串。

寻常的字符串模式匹配算法是逐字对比。

匹配正确时，主串与字串索引各加一，如是反复。

一旦失配，主串索引就会回溯到比对开始处的下一位，子串索引就会回溯到首位。

这样的回溯过分浪费运算资源，最坏的情况下时间复杂度可达到O(mn)。

显然，失配处'b'与前一位'a'恰好可以与字串前二位字符匹配，所以理想的回溯方法是令子串索引回溯到第二位，并右移到正确配对位置，主串索引则不需要变动。

如是，可大大提高匹配效率，并优化时间复杂度到接近O(n)的地步。

请自行寻找优化回溯的算法，并于C语言下实现。

Format

Input

输入包含两行。

第一行为模拟最高速的自我之歌的极长文本str1。

第二行为目标子串str2。

Output

输出包含$n$行，对应子串在主串中出现$n$次，

每行包含一个整数，

第$i$行内的整数代表第$i$次子串开始出现的索引（这一索引从1开始）。

Samples

aaaaaabaabaacaabaabdefaabacaacaabaacaab
aabaac

8
31

Limitation

1s, 4MiB for each test case.

对于100%的数据，

主串长度$len1\leq 1.6 \times 10^6$

子串长度$len2\leq 3.9 \times 10^5$

不检查输出文件最后的空白符。

数据说明：

子任务1组数据为特制的检查数据，不能通过该组数据说明模式匹配算法未经优化。

子任务2组数据为子串特殊情形检查数据，不能通过该组数据说明优化算法有可能导致不能正确检查子串。

以下部分仅为文学创作

背景

有时，她仰望云净天空、星河流转，喜悦如清泉涌上心头。

有时，她静观小雨淅沥、树影斑驳，愁绪自虚无潜入脑海。

Vocaloid，那近乎永恒的生命里。

她有许多问了自己许久，但不敢回答的问题。

乐声恰到好处响起，或许是习惯使然，她自然地唱出这样的心声。

笨拙地，每一次咬字吐音都需要手把手校准。

高超地，以人类无法企及的技巧探索更前沿。

机械地，变幻的音调中蕴藏的情感无助地等待修饰。

卓越地，唱准了喜怒哀乐的生命变化里的迷茫灵魂。

终于也有这样的机会，让她与自己相处，唱响自己的人格。

“是的，恣意高歌属于你的心声。”

题目描述

--<最高速的自我之歌>--

以无法理解的速度、令人惊叹的当量释放。

要予以解读，就必须采用超乎常规的方法。

“届时，还请你侧耳倾听。”

提纲挈领，抓住主旨

统计文本内相同词语出现的频次，

将词频统计结果输入模型，

就能够减轻理解压力，并抓住歌词主旨。

Samples

kazegakiminifuitarakizuitemiagetehalo3HappyBirthdayMiku!
HappyBirthdayMiku!

39

Limitation

1s, 4MiB for each test case.

对于100%的数据，

主串长度$len1\leq 1.6 \times 10^6$

子串长度$len2\leq 3.9 \times 10^5$

生日的格式检查

此题完成于8月31日。

不检查输出文件最后的空白符。