KHOPXAU - Khớp xâu
Xem dạng PDF
Gửi bài giải
Điểm:
2,00 (OI)
Giới hạn thời gian:
0.1s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift
Cho hai xâu ký tự ~s~ và ~t~ có độ dài lần lượt là ~n~ và ~m\ (m ≤ n)~. Xâu ~t~ được gọi là xuất hiện (khớp) tại vị trí ~i~ của xâu ~s~ nếu ~t = s[i..(i + m – 1)]~ (hay ~s[i] = t[1], ..., s[i + m – 1] = t[m]~).
Bạn được cho hai xâu ký tự ~s~ và ~t~ chỉ gồm các chữ cái Latinh thường (‘a’, …, ’z’). hãy liệt kê tất cả các vị trí trên xâu ~s~ mà xâu ~t~ xuất hiện.
Input
- Dòng đầu chứa xâu ~s~;
- Dòng thứ hai chứa xâu ~t~.
Giới hạn:
- ~1 ≤ |s|, |t| ≤ 10^6; |t| ≤ |s|~.
Output
- Ghi trên một dòng các vị trí xuất hiện của xâu ~t~ trong xâu ~s~ (chỉ số của ký tự đầu tiên trong xâu là ~1~, các vị trí được liệt kê theo thứ tự tăng dần, hai số liên tiếp được ghi cách nhau một dấu cách).
Sample
Input #1
abababa
ba
Output #1
2 4 6
Problem source: Chuyên Sơn La Online Judge
Bình luận
A Long hiền khô :)
Ai có bài giải cho mình tham khảo với