2038: KMP查找子串

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：6 Solved：4

Description

给出两个字符串 s1 和 s2，请你求出 s2 在 s1 中所有出现的位置。

Input

第一行为一个字符串，即为 s1。
第二行为一个字符串，即为 s2。

Output

首先输出若干行，每行一个整数，按从小到大的顺序输出 s2 在 s1 中出现的位置。

Sample Input Copy 

ABABABC
ABA

Sample Output Copy 

1
3

HINT

测试点  1≤∣s1∣,∣s2∣≤10^6，s1,s2 中均只含英文字母。