सी ++ में सभी शब्दों के संयोजन के साथ सबस्ट्रिंग

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

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

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

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

  लगेगा।

• 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 – विंडो का आकार डालें

• वापसी उत्तर

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#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, ]