Học thử miễn phí

Tin học 12 HSG — Xử lý xâu nâng cao

Khóa học HSG Tin học 12 làm chủ hai công cụ chuẩn cho mọi bài xử lý xâu thi đấu: băm xâu (string hashing) để so sánh đoạn xâu O(1) sau tiền xử lý O(n), và thuật toán KMP để tìm mẫu O(n+m). Mở rộng sang tiền tố chung dài nhất, kiểm tra đối xứng, Z-function, đếm nhiều mẫu, và bài toán xâu con chung xuất hiện ở nhiều xâu — kết thúc bằng một đề thi mini kết hợp cả hai công cụ dưới ràng buộc thời gian thực tế. Ngôn ngữ giảng dạy là Python.

6 chương6 bài họcKhoảng 10 giờ

Học miễn phí trong ứng dụng

Nội dung khóa học

Băm xâu và mảng hash tiền tố
- Băm xâu (String hashing) — polynomial rolling hash81 phút
KMP và hàm tiền tố
- KMP — hàm tiền tố (prefix function) và tìm mẫu O(n+m)74 phút
So sánh đoạn xâu — LCP, đối xứng, thứ tự từ điển
- So sánh đoạn xâu bằng hashing — chu kỳ, đối xứng, LCP75 phút
Đếm xuất hiện, nhiều mẫu, Z-function
- Ứng dụng tìm mẫu — đếm xuất hiện, nhiều mẫu, xâu lặp75 phút
Bài toán xâu tổng hợp
- Bài toán xâu HSG tổng hợp77 phút
Kỳ thi mini xử lý xâu — tổng kết
- Kỳ thi mini xử lý xâu — tổng kết khóa học69 phút

Nội dung khóa học

Băm xâu và mảng hash tiền tố

KMP và hàm tiền tố

So sánh đoạn xâu — LCP, đối xứng, thứ tự từ điển

Đếm xuất hiện, nhiều mẫu, Z-function

Bài toán xâu tổng hợp

Kỳ thi mini xử lý xâu — tổng kết