Khớp Mẫu Sai Tối Đa Một Ký Tự
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Đề bài
Cho xâu văn bản $T$ và xâu mẫu $P$. Ta nói $P$ khớp xấp xỉ tại vị trí bắt đầu $i$ (đánh chỉ số từ $1$) trong $T$ nếu xâu con $T[i..i+|P|-1]$ khác $P$ ở tối đa 1 vị trí ký tự.
Hãy liệt kê tất cả các vị trí $i$ (theo thứ tự tăng dần) mà $P$ khớp xấp xỉ trong $T$. Nếu không có vị trí nào, in ra -1.
Dữ liệu vào
- Dòng 1: xâu $T$ ($1 \le |T| \le 10^6$).
- Dòng 2: xâu $P$ ($1 \le |P| \le 10^6$).
Dữ liệu ra
- Các vị trí hợp lệ (đánh chỉ số từ $1$) cách nhau bởi dấu cách, hoặc
-1nếu không có.
Ví dụ
| Input | Output |
|---|---|
| abacaba\naba | 1 3 5 |
| abcdef\nxyz | -1 |
Giới hạn
- $1 \le |T|, |P| \le 10^6$, chỉ gồm các chữ cái
'a'–'z'.
Community Discussion