C++ এ সমস্ত শব্দের সংমিশ্রণ সহ সাবস্ট্রিং

ধরুন আমাদের একটি স্ট্রিং, s, এবং আমাদের কাছে শব্দের একটি তালিকাও রয়েছে, অ্যারেতে উপস্থিত শব্দগুলি একই দৈর্ঘ্যের। আমাদেরকে s-তে সাবস্ট্রিং(গুলি) এর সমস্ত প্রারম্ভিক সূচকগুলি খুঁজে বের করতে হবে যা শব্দের প্রতিটি শব্দের সংযোজন ঠিক একবার এবং কোনও হস্তক্ষেপকারী অক্ষর ছাড়াই৷

সুতরাং ইনপুট যদি হয় “barfoothefoobarman” এর মত এবং শব্দগুলো হয় [“foo”, “bar”], তাহলে আউটপুট হবে [0,9]। এর কারণ হল সূচক 0 এবং 9 থেকে শুরু হওয়া সাবস্ট্রিং হল "বারফু" এবং "ফুবার"।

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

• ok() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি স্ট্রিং s, ম্যাপ wordCnt এবং n −

  লাগবে

• s-এর একটি অনুলিপি temp এ তৈরি করুন

• i এর জন্য n থেকে s - 1

  এর পরিসরে

  • যদি তাপমাত্রার আকার 0 এর একাধিক হয়, তাহলে

    • যদি wordCnt-এ temp উপস্থিত না থাকে, তাহলে মিথ্যা ফেরত দিন

    • অন্যথায়

      • যদি wordCnt[temp] 1 হয়, তাহলে wordCnt থেকে temp মুছে দিন, temp একটি খালি স্ট্রিং হিসাবে সেট করুন

      • অন্যথায় wordCnt[temp] এর মান 1 দ্বারা কমিয়ে দিন, temp খালি স্ট্রিং হিসাবে সেট করুন।

  • s[i>

    দ্বারা তাপমাত্রা বাড়ান

• যদি টেম্প wordCnt-এ না থাকে, তাহলে মিথ্যা ফেরত দিন

• অন্যথায়

  • যদি wordCnt[temp] 1 হয়, তাহলে wordCnt থেকে temp মুছে দিন, temp একটি খালি স্ট্রিং হিসাবে সেট করুন

  • অন্যথায় wordCnt[temp] এর মান 1 দ্বারা কমিয়ে দিন, temp খালি স্ট্রিং হিসাবে সেট করুন।

• wordCnt-এর আকার 0

  হলে true রিটার্ন করুন

• মূল পদ্ধতি থেকে, এটি করুন

• যদি a এর আকার 0 হয়, বা b এর আকার 0 হয়, তাহলে খালি অ্যারে ফেরত দিন

• একটি মানচিত্র wordCnt তৈরি করুন, b-এ উপস্থিত স্ট্রিংগুলির ফ্রিকোয়েন্সি wordCnt

  -এ সংরক্ষণ করুন

• ans

  নামে একটি অ্যারে তৈরি করুন

• window :=শব্দের সংখ্যা x প্রতিটি শব্দে অক্ষরের সংখ্যা

• স্ট্রিং-এর একটি কপি তৈরি করুন a in temp

• i এর জন্য রেঞ্জ উইন্ডোতে a – 1

  এর আকার

  • যদি টেম্প সাইজ উইন্ডো দ্বারা বিভাজ্য হয় এবং ঠিক আছে (temp, wordCnt, b[0] এর সাইজ), তাহলে

    • ans

      -এ i – উইন্ডো সন্নিবেশ করুন

  • temp

    এ একটি [i] সন্নিবেশ করান

  • যদি temp> উইন্ডোর আকার হয়, তাহলে 0, 1

    থেকে সাবস্ট্রিং মুছে দিন

• যদি টেম্প সাইজ উইন্ডো দ্বারা বিভাজ্য হয় এবং ঠিক আছে (temp, wordCnt, b[0] এর সাইজ), তাহলে

  • উত্তরের মধ্যে একটি – উইন্ডোর আকার সন্নিবেশ করুন

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

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

#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:
   bool ok(string s, unordered_map <string, int> wordCnt, int n){
      string temp = "";
      for(int i = 0; i < n; i++){
         temp += s[i];
      }
      for(int i = n; i < s.size(); i++){
         if(temp.size() % n == 0){
            if(wordCnt.find(temp) == wordCnt.end())return false;
            else{
               if(wordCnt[temp] == 1){
                  wordCnt.erase(temp);
                  temp = "";
               }
               else{
                  wordCnt[temp]--;
                  temp = "";
               }
            }
         }
         temp += s[i];
      }
      if(wordCnt.find(temp) == wordCnt.end())return false;
      else{
         if(wordCnt[temp] == 1){
            wordCnt.erase(temp);
            temp = "";
         }
         else{
            wordCnt[temp]--;
            temp = "";
         }
      }
      return wordCnt.size() == 0;
   }
   vector<int> findSubstring(string a, vector<string> &b) {
      if(a.size() == 0 || b.size() == 0)return {};
      unordered_map <string, int> wordCnt;
      for(int i = 0; i < b.size(); i++)wordCnt[b[i]]++;
      vector <int> ans;
      int window = b.size() * b[0].size();
      string temp ="";
      for(int i = 0; i < window; i++)temp += a[i];
      for(int i = window; i < a.size(); i++){
         if(temp.size() % window == 0 && ok(temp, wordCnt, b[0].size())){
            ans.push_back(i - window);
         }
         temp += a[i];
         if(temp.size() > window)temp.erase(0, 1);
      }
      if(temp .size() % window ==0 && ok(temp, wordCnt, b[0].size()))ans.push_back(a.size() - window);
      return ans;
   }
};
main(){
   vector<string> v = {"foo", "bar"};
   Solution ob;
   print_vector(ob.findSubstring("barfoothefoobarman", v));
}

ইনপুট

1,2,3,4,5,6,7
3

আউটপুট

[0, 9, ]