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

Thuật toán Knuth-Morris-Pratt (KMP) so khớp mẫu xâu

Trong công cụ kiểm duyệt và phát hiện đạo văn tại AI Empire Academy, hệ thống cần tìm kiếm sự xuất hiện của một đoạn mã mẫu P (Pattern) bên trong văn bản mã nguồn lớn T (Text). Với

C++Nâng cao40 phút

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

Điểm và code bạn nộp đượ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ủ đề

kmpstring algorithmsprefix functionpattern matching

Kiến thức tiên quyết: std string, std vector, two pointers.

Nội dung đề bài

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

  • Hiểu và cài đặt hàm tiền tố pi (Prefix Function / Longest Prefix Suffix - LPS) trong O(|P|).
  • Áp dụng thuật toán Knuth-Morris-Pratt để so khớp mẫu không quay lui trên văn bản trong O(|T|).
  • Xử lý chuẩn xác các trường hợp mẫu xuất hiện gối đầu (overlapping occurrences).

Mô tả bài toán

Trong công cụ kiểm duyệt và phát hiện đạo văn tại AI Empire Academy, hệ thống cần tìm kiếm sự xuất hiện của một đoạn mã mẫu P (Pattern) bên trong văn bản mã nguồn lớn T (Text). Với các đoạn văn bản dài tới 106 ký tự, các thuật toán duyệt vét cạn O(|T| × |P|) sẽ bị quá thời gian. Bạn cần sử dụng thuật toán Knuth-Morris-Pratt (KMP) để tìm tất cả các vị trí xuất hiện của P trong T với độ phức tạp tuyến tính O(|T| + |P|).

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: Xâu mẫu P (1 ≤ |P| ≤ 105).
  • Cả hai xâu chỉ gồm các chữ cái tiếng Anh in thường và in hoa (a-z, A-Z), phân biệt chữ hoa chữ thường.

Output

  • Dòng 1: Một số nguyên duy nhất là số lần xâu P xuất hiện trong T.
  • Dòng 2: Các chỉ số bắt đầu (theo thứ tự tăng dần, đánh số từ 1) của những lần xuất hiện của P trong T, cách nhau bởi một khoảng trắng. Nếu P không xuất hiện lần nào, dòng này để trống.

Ràng buộc

  • 1 ≤ |T| ≤ 106.
  • 1 ≤ |P| ≤ 105.
  • Thời gian chạy: 1000ms.
  • Bộ nhớ tối đa: 256MB.

Ví dụ 1

Input

AABAACAADAABAABA
AABA

Output

3
1 10 13

Ví dụ 2

Input

AAAAA
AAA

Output

3
1 2 3

Ví dụ 3

Input

AIEMPIRE
PYTHON

Output

0
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 đề

Thuật toán Z-Algorithm xây dựng mảng Z-Function trong O(N)
Nâng cao35p
Cây tiền tố Trie: Từ điển tra cứu và đếm tiền tố
Nâng cao45p
Tự động Aho-Corasick tìm kiếm đồng thời nhiều xâu mẫu
Nâng cao50p
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.

Nhóm Zalo