Tìm kiếm xâu mẫu bằng KMP
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho hai xâu ký tự $T$ (văn bản) và $P$ (mẫu) chỉ gồm các chữ cái tiếng Anh viết thường. Hãy tìm tất cả các vị trí bắt đầu (đánh số từ $1$) mà xâu $P$ xuất hiện như một xâu con liên tiếp trong $T$.
Dữ liệu vào
- Dòng đầu tiên chứa xâu $T$.
- Dòng thứ hai chứa xâu $P$.
Dữ liệu ra
In ra số lần xuất hiện ở dòng đầu tiên. Nếu có ít nhất 1 lần xuất hiện, dòng thứ hai in ra các vị trí tìm được theo thứ tự tăng dần.
Ví dụ
| Input | Output |
|---|---|
| abababa aba |
3 1 3 5 |
Giới hạn
$1 \le |P| \le |T| \le 10^6$.
Community Discussion