So Khớp Xâu Với Ký Tự Đại Diện
Points
42
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Đề bài
Cho xâu văn bản $S$ và xâu mẫu $P$ chỉ gồm các chữ cái tiếng Anh viết thường (a–z) và riêng xâu mẫu $P$ có thể chứa ký tự đại diện '?' (khớp với bất kỳ chữ cái nào). Hãy tìm tất cả các vị trí bắt đầu (1-indexed) trong $S$ mà $P$ khớp với xâu con tương ứng của $S$.
Dữ liệu vào
- Dòng đầu chứa xâu $S$ ($1 \le |S| \le 10^5$).
- Dòng thứ hai chứa xâu $P$ ($1 \le |P| \le |S|$).
Dữ liệu ra
- Dòng đầu in ra số lượng vị trí khớp.
- Dòng thứ hai in ra các vị trí khớp theo thứ tự tăng dần, cách nhau bởi dấu cách (nếu không có vị trí nào, để trống dòng thứ hai).
Ví dụ
| Input | Output |
|---|---|
| abacaba a?a |
3 1 3 5 |
| abcde f?g |
0 |
Giới hạn
- $1 \le |P| \le |S| \le 10^5$
Community Discussion