Tìm kiếm xâu mẫu bằng KMP

Buổi 54 — KMP & Z-function Buổi 69-70 — Mock Tổng hợp Strings
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$.

Draft saved