পাইথনে T-এ একটি স্ট্রিং S-এর সমস্ত অ্যানাগ্রামের সূচনা সূচক খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের দুটি স্ট্রিং S এবং T আছে, আমাদেরকে T-তে S-এর অ্যানাগ্রামের সমস্ত সূচনা সূচক খুঁজে বের করতে হবে। স্ট্রিংগুলি শুধুমাত্র ছোট হাতের অক্ষর নিয়ে গঠিত এবং S এবং T উভয় স্ট্রিংয়ের দৈর্ঘ্য 20 এবং 100 এর বেশি হবে না।

সুতরাং, যদি ইনপুটটি S ="cab" T ="bcabxabc" এর মত হয়, তাহলে আউটপুট হবে [0, 1, 5, ], সাবস্ট্রিং "bca", "cab" এবং "abc" হিসাবে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব:

• একটি মানচিত্র সংজ্ঞায়িত করুন m, n :=s এর আকার, বাম সেট করুন :=0, ডান :=0, কাউন্টার :=p এর আকার

• একটি অ্যারে সংজ্ঞায়িত করুন ans

• m

  ম্যাপে p অক্ষরের ফ্রিকোয়েন্সি সংরক্ষণ করুন

• ডানের জন্য :=0 থেকে n – 1

  • যদি m এর s[সঠিক] থাকে এবং m[s[right]] শূন্য হয়, তাহলে m[s[right]] 1 দ্বারা কমান, কাউন্টার 1 দ্বারা হ্রাস করুন এবং কাউন্টার =0 হলে, উত্তরে বাম দিকে সন্নিবেশ করুন

  • অন্যথায়

    • যখন বাম <ডান,

      • যদি m এ s[left] না থাকে, তাহলে কাউন্টার 1 দ্বারা বাড়ান এবং m[s[left]] 1 দ্বারা বাড়ান

      • 1 দ্বারা বাম বাড়ান

      • যদি m এর s[ডান] থাকে এবং m[s[ডান]] শূন্য হয়, তাহলে ডানদিকে 1 কমিয়ে লুপ থেকে বেরিয়ে আসুন

    • যদি m-এর কোনো s[left] না থাকে, তাহলে লেফট সেট করুন :=right + 1

• উত্তর ফেরত দিন

আরও ভালভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি:

উদাহরণ

#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("bcabxabc", "cab")) ;
}

ইনপুট

"bcabxabc", "cab"

আউটপুট

[0, 1, 5, ]