Ghép xâu

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho xâu \(A\) và xâu \(B\) chỉ gồm các chữ cái thường. Xâu \(B\) được gọi là xuất hiện tại vị trí \(i\) của xâu \(A\) nếu: \(A[i] = B[1], A[i+1] = B[2], ..., A[i+length(B)-1] = B[length(B)]\). (\(length(B)\) là độ dài của xâu \(B\))

Yêu cầu: Hãy tìm tất cả các vị trí mà \(B\) xuất hiện trong \(A\).

Input

  • Dòng 1: xâu \(A\).
  • Dòng 2: xâu \(B\).
  • Độ dài \(A, B\) không quá \(1000000\).

Output

  • Ghi ra các vị trí tìm được trên 1 dòng (thứ tự tăng dần). Nếu \(B\) không xuất hiện trong \(A\) thì bỏ trắng.

Example

Test 1

Input
aaaaa
aa
Output
1 2 3 4

Nguồn: vn.spoj.com


Bình luận