Học thử miễn phí
Bài học PremiumTin 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 phầnKhoảng 10 giờ
Học Chương 1 miễn phíNội dung bài học
Chương 1 mở xem thử, các chương còn lại nằm trong gói Premium.
Băm xâu và mảng hash tiền 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útPremium
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útPremium
Đế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útPremium
Bài toán xâu tổng hợp
- Bài toán xâu HSG tổng hợp77 phútPremium
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útPremium