Tìm Mẫu Trong Văn Bản

Buổi 53 — String Hashing
Points
18
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho một chuỗi văn bản $T$ và một chuỗi mẫu $P$. Hãy xác định xem chuỗi mẫu $P$ có xuất hiện trong văn bản $T$ hay không. Nếu có, in ra vị trí xuất hiện đầu tiên (đánh số từ 1).

Sử dụng thuật toán Rabin-Karp để giải bài toán này.

Dữ liệu vào
  • Dòng đầu tiên chứa chuỗi $T$.
  • Dòng thứ hai chứa chuỗi $P$.
Dữ liệu ra
  • Nếu $P$ xuất hiện trong $T$, in ra vị trí xuất hiện đầu tiên (1-indexed).
  • Ngược lại in ra -1.
Ví dụ
Input Output
abcabc\nabc 1
abcdef\nxyz -1
Giới hạn
  • $1 \le |P| \le |T| \le 10^6$
  • Các chuỗi chỉ chứa ký tự in thường từ a đến z.
Draft saved