Xâu con

View as PDF
Submit solution
Points: 0.09 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 )}~.

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.

Sample Input

aaaaa
aa

Sample Output

1 2 3 4

Comments

Please read the guidelines before commenting.


  • -46
    phu142857   commented on 13, Jul, 2021, 10:00

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 20
    PPAP_1264589   commented on 14, Jun, 2021, 0:22

    Nếu dùng thuật Hash các bạn chú ý để long long nhé. Base cũng không nên quá lớn


    • 4
      kazamahoang   commented on 2, Jul, 2021, 20:57

      Tại sao vậy bạn


      • 5
        PPAP_1264589   commented on 4, Jul, 2021, 21:23

        Bởi trường hợp xấu nhất việc lấy mã hash có thể tràn số do vượt quá kiểu int :/

        Base không nên quá lớn cũng vì lý do này (theo kinh nghiệm của mình) :D


        • 2
          kazamahoang   commented on 5, Jul, 2021, 16:50 ← edited

          Thế tràn bộ nhớ thì sao bạn

          với cả base không lớn thì sai số á :((


          • 0
            abcd1234   commented on 9, Jan, 2022, 21:06 ← edited

            tràn bộ nhớ thì sẽ bị MLE(memory limited exceed) đó bạn :)