หาทุกตำแหน่งของ Anagram ในสตริงใน C++

สมมติว่าเรามีสตริง s และสตริง p ไม่ว่าง ต้องหาดัชนีเริ่มต้นทั้งหมดของ anagram ของ p ใน s สตริงประกอบด้วยตัวอักษรพิมพ์เล็ก ความยาวไม่เกิน 20 และ 100

ตัวอย่าง: s: "cbaebabacd", p: "abc" ผลลัพธ์: [0, 6]
ดัชนี 0 คือ "cba", ดัชนี 6 คือ "bac" ทั้งคู่เป็น anagram ของ "abc"

ขั้นตอนการแก้ปัญหา (Sliding Window + Hash Map)

• แผนที่ m เก็บความถี่ตัวอักษรใน p
• n := s.size(), left := 0, right := 0, counter := p.size()
• อาร์เรย์ ans
• วน right จาก 0 ถึง n-1:
  • ถ้า s[right] อยู่ใน m และ m[s[right]] > 0:
    • ลด m[s[right]] และ counter
    • ถ้า counter == 0 ใส่ left เข้า ans
  • มิฉะนั้น (ตัวอักษรไม่ตรงหรือเกิน):
    • while left < right:
      • ถ้า s[left] อยู่ใน m เพิ่ม counter และ m[s[left]]
      • left++
      • ถ้า s[right] กลับมาใช้ได้ (m[s[right]] > 0) ลด right และ break
    • ถ้า s[left] ไม่อยู่ใน m ตั้ง left := right + 1
• คืน ans

ตัวอย่างโค้ด (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();
        int left = 0, right = 0;
        int counter = p.size();
        vector <int> ans;
        for(int i = 0; i < p.size(); i++) m[p[i]]++;
        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"));
}

อินพุต

"cbaebabacd" "abc"

เอาต์พุต

[0, 6, ]