स्ट्रिंग (एस) में सबस्ट्रिंग के शुरुआती सूचकांक खोजें जो सी ++ में एक सूची (एल) से सभी शब्दों को जोड़कर बनाया गया है

मान लीजिए कि हमारे पास एक स्ट्रिंग है, s, और हमारे पास कुछ शब्दों के साथ एक और सूची है, ये शब्द समान लंबाई के हैं। हमें s में सबस्ट्रिंग (ओं) के सभी शुरुआती सूचकांकों को खोजना होगा जो शब्दों में प्रत्येक शब्द का एक बार और बिना किसी हस्तक्षेप के वर्णों का एक संयोजन है।

तो अगर इनपुट "वर्डगुडगुडगुडवर्ड" जैसा है और शब्द ["शब्द", "अच्छा"] हैं, तो आउटपुट [0,12] होगा। ऐसा इसलिए है क्योंकि इंडेक्स 0 और 12 से शुरू होने वाले सबस्ट्रिंग "वर्डगूड" और "गुडवर्ड" हैं।

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

• ओके () नामक एक विधि को परिभाषित करें, इसमें स्ट्रिंग एस, मैप वर्डकंट और एन -

  लगेगा।

• s को अस्थायी में कॉपी करें

• मैं के लिए n श्रेणी में s – 1 के आकार के लिए

  • यदि अस्थायी का आकार 0 का गुणज है, तो

    • यदि वर्डकंट में अस्थायी मौजूद नहीं है, तो झूठी वापसी करें

    • अन्यथा

      • अगर wordCnt[temp] 1 है, तो wordCnt से अस्थायी हटाएं, अस्थायी को एक खाली स्ट्रिंग के रूप में सेट करें

      • अन्यथा wordCnt[temp] के मान को 1 से कम करें, अस्थायी को खाली स्ट्रिंग के रूप में सेट करें।

  • तापमान में s[i]

    की वृद्धि करें

• यदि अस्थायी शब्द वर्ड में नहीं है, तो झूठी वापसी करें

• अन्यथा

  • अगर wordCnt[temp] 1 है, तो wordCnt से अस्थायी हटाएं, अस्थायी को एक खाली स्ट्रिंग के रूप में सेट करें

  • अन्यथा wordCnt[temp] के मान को 1 से कम करें, अस्थायी को खाली स्ट्रिंग के रूप में सेट करें।

• वर्डकंट का आकार 0 होने पर सही लौटें

• मुख्य विधि से यह करें

• यदि a का आकार 0 है, या b का आकार 0 है, तो खाली सरणी लौटाएं

• एक नक्शा वर्डकंट बनाएं, बी में मौजूद स्ट्रिंग्स की फ्रीक्वेंसी को वर्डसीएनटी में स्टोर करें

• उत्तर नामक एक सरणी बनाएं

• विंडो:=शब्दों की संख्या x प्रत्येक शब्द में वर्णों की संख्या

• स्ट्रिंग ए की एक प्रति अस्थायी में बनाएं

• मैं के लिए रेंज विंडो में a – 1 के आकार के लिए

  • यदि अस्थायी आकार खिड़की से विभाज्य है और कॉल ठीक है (अस्थायी, वर्डकंट, बी का आकार [0]), तो

    • इन्सर्ट i - विंडो को ans में

  • [i] को टेम्परेचर में डालें

  • यदि अस्थायी> विंडो का आकार है, तो 0, 1 से सबस्ट्रिंग हटाएं

• यदि अस्थायी आकार खिड़की से विभाज्य है और कॉल ठीक है (अस्थायी, वर्डकंट, बी का आकार [0]), तो

  • ans में a – विंडो का आकार डालें

• वापसी उत्तर

उदाहरण (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:
   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 = {"word","good"};
   Solution ob;
   print_vector(ob.findSubstring("wordgoodgoodgoodword", v));
}

इनपुट

“wordgoodgoodgoodword”, {"word","good"}

आउटपुट

[0, 12, ]