• Dùng ctdl map để lưu số lần xuất hiện của từng ký tự của chuỗi ~A~, và số lần xuất hiện của từng ký tự của chuỗi ~B~ trong khoảng độ dài ~n~. Ở mỗi bước ta cập nhật lại số lần xuất hiện các ký tự của chuỗi ~B~ và kiểm tra, đồng thời cập nhật kết quar.
• Đpt: ~O(n \times \log n)~

Code tham khảo

#include<bits/stdc++.h>

using namespace std;

int n, m;
string s, t;
map<char, int> cnt_s, cnt_t;

bool ok() {
    for (char c = 'a'; c <= 'z'; c++) if (cnt_s[c] != cnt_t[c]) return false;
    for (char c = 'A'; c <= 'Z'; c++) if (cnt_s[c] != cnt_t[c]) return false;
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> s >> t;
    for (int i = 0; i < n; i++) {
        cnt_s[s[i]]++;
        cnt_t[t[i]]++;
    }
    int ans = ok();
    for (int i = n; i < m; i++) {
        cnt_t[t[i]]++;
        cnt_t[t[i - n]]--;
        ans += ok();
    }
    cout << ans;
    return 0;
}