Hướng dẫn giải của [TS10 Thái Nguyên 2025 - 2026] Tìm xâu kí tự
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Dùng cửa sổ trượt độ dài ~|A|~ trên xâu ~B~. Ta lưu bảng tần số ký tự của ~A~ và bảng tần số của cửa sổ hiện tại.
Khi trượt cửa sổ sang phải, bỏ ký tự rời khỏi cửa sổ và thêm ký tự mới. Nếu hai bảng tần số bằng nhau thì đoạn hiện tại là một hoán vị của ~A~.
Độ phức tạp ~O(|B|\times C)~ nếu so sánh trực tiếp trên bảng kích thước ~C~, với ~C=256~ là hằng số.
Bình luận