सी ++ में एक स्ट्रिंग में सभी एनाग्राम खोजें

मान लीजिए कि हमारे पास एक स्ट्रिंग s और एक गैर-रिक्त स्ट्रिंग p है, हमें s में p के विपर्यय के सभी प्रारंभ सूचकांकों को खोजना होगा। स्ट्रिंग्स में केवल लोअरकेस अक्षर होते हैं और दोनों स्ट्रिंग्स s और p की लंबाई 20 और 100 से अधिक नहीं होगी। इसलिए उदाहरण के लिए, यदि s:"cbaebabacd" p:"abc", तो आउटपुट [0, 6 होगा। ], सूचकांक 0 पर, यह "cba" है, और दूसरा "bac" है, ये "abc" के विपर्यय हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मानचित्र को परिभाषित करें m, n:=s का आकार, बाएँ सेट करें:=0, दाएँ:=0, काउंटर:=p का आकार

• एक सरणी को परिभाषित करें ans

• p में वर्णों की आवृत्ति को मानचित्र m में संग्रहीत करें

• दाईं ओर :=0 से n - 1

  • यदि m में s[right] है और m[s[right]] शून्य नहीं है, तो m[s[right]] को 1 से घटाएं, काउंटर को 1 से घटाएं और यदि काउंटर =0 है, तो बाएं को उत्तर में डालें

  • अन्यथा

    • जबकि बाएं <दाएं,

      • यदि s[बाएं] m में मौजूद नहीं है, तो काउंटर को 1 से बढ़ाएं और m[s[बाएं]] को 1 से बढ़ाएं

      • बाईं ओर 1

        . बढ़ाएं

      • अगर m में s[right] है और m[s[right]] शून्य नहीं है, तो 1 से दाएं घटाएं और लूप से बाहर आएं

    • अगर m में कोई s[बाएं] नहीं है, तो बाएं सेट करें:=दायां + 1

• वापसी उत्तर

उदाहरण(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;
   }
};
main(){
   Solution ob;
   print_vector(ob.findAnagrams("cbaebabacd", "abc")) ;
}

इनपुट

"cbaebabacd"
"abc"

आउटपुट

[0, 6, ]