Khớp Mẫu Sai Tối Đa Một Ký Tự

Buổi 54 — KMP & Z-function
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề 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 -1 nế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'.
Draft saved