Đăng ký
cpp-049Đọc toàn bộ đề miễn phí

Tự động Aho-Corasick tìm kiếm đồng thời nhiều xâu mẫu

Hệ thống kiểm duyệt nội dung của AI Empire Academy cần tìm kiếm sự xuất hiện của K từ khóa mẫu P1, P2, …, PK bên trong một đoạn văn bản T.

C++Nâng cao50 phút

Tiến độ của tôi ở bài này

Điểm được lưu vào tài khoản sau khi chấm bài.

Đang tải điểm của bạn…

Kiến thức và chủ đề

aho corasickstringstrieautomatabfs

Kiến thức tiên quyết: trie, kmp, bfs.

Nội dung đề bài

Mục tiêu kiến thức

  • Hiểu cấu trúc Tự động Aho-Corasick kết hợp giữa Cây tiền tố (Trie) và Hàm tiền tố KMP.
  • Xây dựng liên kết thất bại (Suffix/Failure Link) bằng BFS tầng.
  • Đếm tổng số lần xuất hiện của tất cả các mẫu trong văn bản T trong thời gian tuyến tính O(|T| + ∑ |Pi|).

Mô tả bài toán

Hệ thống kiểm duyệt nội dung của AI Empire Academy cần tìm kiếm sự xuất hiện của K từ khóa mẫu P1, P2, …, PK bên trong một đoạn văn bản T.

Hãy tính tổng số lần xuất hiện của tất cả các từ khóa trong T (nếu một từ xuất hiện nhiều lần hoặc nhiều từ cùng xuất hiện tại một vị trí, đều được tính riêng rẽ).

Quy ước nộp bài

  • Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
  • Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
  • Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
  • Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Input

  • Dòng 1: Xâu văn bản T (1 ≤ |T| ≤ 106).
  • Dòng 2: Một số nguyên K (1 ≤ K ≤ 105) — số lượng mẫu.
  • K dòng tiếp theo: Mỗi dòng gồm một xâu mẫu Pi. Tổng độ dài của tất cả các xâu mẫu ≤ 5 · 105.
  • Các xâu chỉ gồm các chữ cái in thường tiếng Anh 'a' đến 'z'.

Output

  • In ra một số nguyên duy nhất là tổng số lần xuất hiện của các từ khóa trong văn bản T.

Ràng buộc

  • 1 ≤ |T| ≤ 106.
  • Tổng độ dài các mẫu ≤ 5 · 105.
  • Thời gian chạy: 1000ms.
  • Bộ nhớ tối đa: 256MB.

Ví dụ 1

Input

ushers
3
he
she
hers

Output

3
*Giải thích:*
- 'he' xuất hiện 1 lần trong "ushers" (vị trí 3).
- 'she' xuất hiện 1 lần trong "ushers" (vị trí 2).
- 'hers' xuất hiện 1 lần trong "ushers" (vị trí 3).
Tổng cộng: $1 + 1 + 1 = 3$ lần.
3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.
Phân tích lời giảiGiải thích hướng tư duy và thuật toán.
Code tham khảoDùng để đối chiếu sau khi tự làm.

Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.

Bài tập liên quan cùng chuyên đề

Cây tiền tố Trie: Từ điển tra cứu và đếm tiền tố
Nâng cao45p
Máy tự động hậu tố Suffix Automaton (SAM) đếm số xâu con phân biệt
Nâng cao50p
Cây đối xứng (Palindromic Tree / EerTree): Đếm xâu con đối xứng phân biệt
Nâng cao55p
Thuật toán Manacher tìm xâu con đối xứng (Palindrome) dài nhất trong O(N)
Nâng cao35p

Góp ý & báo lỗi bài tập

Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.