Tổng Số Lần Khớp Mẫu

Buổi 55 — Trie & Aho-Corasick
Points
44
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho $N$ xâu mẫu $P_1, P_2, \dots, P_N$ và một xâu văn bản $T$. Hãy đếm tổng số lần xuất hiện của tất cả các xâu mẫu trong $T$ (các lần xuất hiện có thể chồng lấn nhau, và nếu hai mẫu trùng nhau đều được tính riêng).

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$).
  • $N$ dòng tiếp theo, mỗi dòng chứa một xâu mẫu $P_i$.
  • Dòng cuối cùng chứa xâu văn bản $T$.
Dữ liệu ra
  • Một số nguyên duy nhất là tổng số lần xuất hiện.
Ví dụ
Input Output
4
he
she
hers
his
ahishers
4
Giới hạn
  • Tổng độ dài các xâu mẫu không vượt quá $5 \cdot 10^5$.
  • $|T| \le 5 \cdot 10^5$, các ký tự đều thuộc a–z.
Draft saved