Khớp mẫu xấp xỉ sai khác tối đa 1 ký tự

General
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho hai xâu $T$ và $P$ ($|P| \le |T|$). Hãy đếm số vị trí bắt đầu $i$ ($0 \le i \le |T| - |P|$) sao cho xâu con $T[i..i+|P|-1]$ khác với $P$ tại tối đa 1 vị trí.

Dữ liệu vào

Dòng đầu chứa xâu $T$. Dòng hai chứa xâu $P$.

Dữ liệu ra

In ra số lượng vị trí $i$ thỏa mãn.

Ví dụ
Input Output
abacaba
aba
3
Giới hạn
  • $1 \le |P| \le |T| \le 10^5$
Draft saved