Hướng dẫn giải của Câu 1 (Tuyển sinh chuyên Tin Bình Dương 2023-2024)
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.
Hướng dẫn giải
Cần đếm số vị trí bắt đầu ~i~ trong chuỗi ~B~ sao cho đoạn ~B[i..i+n-1]~ là một hoán vị của chuỗi ~A~. Hai chuỗi có thể chứa cả chữ hoa và chữ thường, nên có 52 loại ký tự khác nhau. Nếu ~n > m~ thì đáp án là 0.
Sub 1: Vét cạn — ~O(m \cdot n \log n)~, dùng khi ~m \le 10^4~
Sắp xếp chuỗi ~A~ một lần. Với mỗi vị trí bắt đầu, lấy đoạn dài ~n~, sắp xếp đoạn đó rồi so với ~A~ đã sắp xếp. Nếu bằng nhau thì đoạn là hoán vị của ~A~. Nếu chỉ nộp sub này: đúng 33/40 test (đúng hết các test trong miền, 7 test lớn bị quá giờ).
Sub 2: Cửa sổ trượt với tần suất — ~O(n + m)~
Đếm số lần xuất hiện của 52 ký tự trong ~A~. Giữ một cửa sổ dài ~n~ trượt trên ~B~, đồng thời đếm số ký tự mà tần suất trong cửa sổ khác tần suất trong ~A~ (biến ~diff~). Mỗi lần thêm hoặc bớt một ký tự chỉ cập nhật ~diff~ trong ~O(1)~. Cửa sổ là hoán vị khi ~diff = 0~. Bẫy cần chú ý: khởi tạo ~diff~ bằng số loại ký tự có mặt trong ~A~ (vì lúc đầu cửa sổ rỗng); chỉ đếm cửa sổ khi đã đủ ~n~ ký tự. Nếu chỉ nộp sub này: đúng 40/40 test.
Chương trình hoàn chỉnh
main đọc ~n, m~ và hai chuỗi. Nếu ~m \le 10^4~ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, m;
string A, B;
// Sub 1: vet can O(m * n log n) - voi moi vi tri bat dau, lay doan dai n, sap xep va so voi A da sap xep
void sub1() {
string sa = A;
sort(sa.begin(), sa.end());
int cnt = 0;
for (int i = 0; i + n <= m; i++) {
string w = B.substr(i, n);
sort(w.begin(), w.end());
if (w == sa) cnt++; // doan la hoan vi cua A
}
cout << cnt << "\n";
}
// Chi so cua ky tu: chu hoa 0..25, chu thuong 26..51
int idx(char c) {
return (c >= 'a' && c <= 'z') ? c - 'a' + 26 : c - 'A';
}
// Sub 2: cua so truot dai n, so sanh tan suat 52 chu cai. Do phuc tap O(n + m).
void sub2() {
int cntA[52] = {0}, cntW[52] = {0};
for (char c : A) cntA[idx(c)]++;
// diff = so chu cai ma tan suat trong cua so khac tan suat cua A
int diff = 0;
for (int k = 0; k < 52; k++)
if (cntA[k] != 0) diff++; // luc dau cua so rong, moi ky tu xuat hien trong A la mot chenh lech
int cnt = 0;
for (int i = 0; i < m; i++) {
// them ky tu B[i] vao cua so
int c = idx(B[i]);
if (cntW[c] == cntA[c]) diff++;
cntW[c]++;
if (cntW[c] == cntA[c]) diff--;
// bo ky tu B[i-n] khoi cua so khi cua so da vuot qua do dai n
if (i >= n) {
int d = idx(B[i - n]);
if (cntW[d] == cntA[d]) diff++;
cntW[d]--;
if (cntW[d] == cntA[d]) diff--;
}
if (i >= n - 1 && diff == 0) cnt++; // cua so cuoi tai vi tri i co dung n ky tu va trung tan suat
}
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
cin >> A >> B;
n = A.size(); // do dai thuc te cua A va B
m = B.size();
if (n > m) { cout << 0 << "\n"; return 0; }
if (m <= 10000) sub1(); // du lieu nho
else sub2(); // du lieu lon
return 0;
}
Bình luận