solution

Cho $k$ xâu mẫu $P_1, \dots, P_k$ 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 mẫu trong $T$ (cho phép chồng lấn; nếu nhiều mẫu giống nhau thì đếm riêng từng mẫu; mỗi vị trí khớp của mỗi mẫu tính một lần).

Sử dụng máy tự động Aho–Corasick để xử lý trong $O(\sum|P_i| + |T| + \text{số lần khớp})$ — ở đây ta chỉ cần tổng số nên dùng đếm gộp theo liên kết suffix.

Ví dụ: Mẫu ab, bc trong abc: ab khớp tại vị trí $1$, bc khớp tại vị trí $2$, tổng $2$.