String Search - String Search

Time Limit : 1 sec, Memory Limit : 262144 KB

文字列検索

文字列 T の中から文字列 P と一致する部分を探してください。P と一致する部分について、文字列 T の左端の位置 i (i = 0, 1, ..., Tの長さ -1) を順番にすべて報告してください。

入力

1行目に文字列 T、2行目に文字列 P が与えられる。

出力

各出現位置を1行に、順番に出力する。

制約

  • 1 ≤ T の長さ ≤ 1000000
  • 1 ≤ P の長さ ≤ 10000
  • 文字列は、英小文字、英大文字、数字のみで構成されている。

入力例 1

aabaaa
aa

出力例 1

0
3
4

入力例 2

xyzz
yz

出力例 2

1

入力例 3

abc
xyz

出力例 3


出力なし。