Xâu con
Xem dạng PDF
Gửi bài giải
Điểm:
0,09 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, 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
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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
Hash thì để mod vừa phải và int cũng được để buff tốc độ chạy mặc dù không quá nhiều :D
Tại sao vậy bạn
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
Thế tràn bộ nhớ thì sao bạn
với cả base không lớn thì sai số á :((
tràn bộ nhớ thì sẽ bị MLE(memory limited exceed) đó bạn :)