Tìm tất cả vị trí anagram trong chuỗi C++

Cho chuỗi s và p (khác rỗng), tìm tất cả chỉ số bắt đầu của anagram của p trong s. Chỉ chứa chữ thường, độ dài ≤ 20100.

Ví dụ: s="cbaebabacd", p="abc" → Kết quả: [0,6]. Tại 0: "cba", tại 6: "bac".

Giải thuật (Cửa sổ trượt + Map tần suất)

1. Map m lưu tần suất ký tự trong p, counter = p.size().
2. Duyệt right từ 0 đến n-1:
3. Nếu s[right] trong m và count > 0: giảm count, giảm counter. Nếu counter==0 → thêm left vào kết quả.
4. Ngược lại: thu hẹp cửa sổ từ left cho đến khi hợp lệ hoặc left=right+1.
5. Trả về danh sách chỉ số.

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<auto> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) cout << v[i] << ", ";
    cout << "]" << endl;
}

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        map<char, int> m;
        int n = s.size(), left = 0, counter = p.size();
        vector<int> ans;
        for(char c : p) m[c]++;
        for(int right = 0; right < n; right++) {
            if(m.find(s[right]) != m.end() && m[s[right]]) {
                m[s[right]]--; counter--;
                if(counter == 0) ans.push_back(left);
            } else {
                while(left < right) {
                    if(m.find(s[left]) != m.end()) { counter++; m[s[left]]++; }
                    left++;
                    if(m.find(s[right]) != m.end() && m[s[right]]) { right--; break; }
                }
                if(m.find(s[left]) == m.end()) left = right + 1;
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    print_vector(ob.findAnagrams("cbaebabacd", "abc"));
    return 0;
}

Đầu vào

"cbaebabacd" "abc"

Đầu ra

[0, 6, ]