Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

सभी शब्दों के संयोजन वाला सबस्ट्रिंग - C++ प्रोग्राम


मान लीजिए हमारे पास एक स्ट्रिंग s है, और हमारे पास शब्दों की एक सूची भी है, ऐरे में मौजूद सभी शब्द समान लंबाई के हैं। हमें s में उन सभी सबस्ट्रिंग के प्रारंभिक इंडेक्स ढूंढने हैं जो words में प्रत्येक शब्द का ठीक एक बार संयोजन है और बिना किसी हस्तक्षेप वाले वर्णों के।

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

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

  • ok() नामक एक विधि परिभाषित करें, जो स्ट्रिंग s, मैप wordCnt और n लेगा −

  • s की एक प्रति temp में बनाएं

  • i को n से s के आकार - 1 तक की रेंज में

    • यदि temp का आकार 0 का गुणक है, तो

      • यदि temp wordCnt में मौजूद नहीं है, तो false लौटाएं

      • अन्यथा

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

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

    • temp को s[i] से बढ़ाएं

  • यदि temp wordCnt में नहीं है, तो false लौटाएं

  • अन्यथा

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

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

  • true लौटाएं जब wordCnt का आकार 0 हो

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

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

  • wordCnt नामक एक मैप बनाएं, b में मौजूद स्ट्रिंग्स की आवृत्ति को wordCnt में स्टोर करें

  • ans नामक एक ऐरे बनाएं

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

  • स्ट्रिंग a की एक प्रति temp में बनाएं

  • i को window से a के आकार - 1 तक की रेंज में

    • यदि temp का आकार window से विभाज्य है और ok(temp, wordCnt, b[0] का आकार) कॉल करें, तो

      • i - window को ans में डालें

    • a[i] को temp में डालें

    • यदि temp का आकार > window है, तो 0, 1 से सबस्ट्रिंग हटाएं

  • यदि temp का आकार window से विभाज्य है और ok(temp, wordCnt, b[0] का आकार) कॉल करें, तो

    • a के आकार - window को ans में डालें

  • ans लौटाएं

उदाहरण 

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

#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)); }

इनपुट

"barfoothefoobarman", ["foo", "bar"]

आउटपुट

[0, 9, ]

  1. कुछ शर्तों के साथ ग्राफ बनाने के लिए C++ प्रोग्राम कुछ शर्तों के साथ ग्राफ बनाने के लिए C++ प्रोग्राम

    मान लीजिए हमारे पास दो संख्याएं N और K हैं। N तत्वों वाला एक निदेशित ग्राफ पर विचार करें। N शीर्ष निम्नलिखित शर्तों को पूरा करते हैं: ग्राफ सरल और जुड़ा हुआ है शीर्ष 1 से N तक गिने जाते हैं मान लें M ग्राफ में किनारों की संख्या है। किनारों को 1 से M तक गिना जाता है। किनारे की लंबाई 1 है। और किनारा

  1. C++ में डौबली लिंक्ड लिस्ट का आकार ढूंढना C++ में डौबली लिंक्ड लिस्ट का आकार ढूंढना

    इस समस्या में, हमें एक डौबली लिंक्ड लिस्ट दी गई है। हमारा कार्य C++ में डौबली लिंक्ड लिस्ट का आकार ढूंढने के लिए एक प्रोग्राम बनाना है। डौबली लिंक्ड लिस्ट एक विशेष प्रकार की लिंक्ड लिस्ट है जिसमें नेविगेशन दोनों तरीकों से संभव है, आगे और पीछे आसानी से सिंगल लिंक्ड लिस्ट की तुलना में। डौबली लिंक्ड ल

  1. - C++ में यूजर डिफाइंड साइज़ के साथ 2D वेक्टर

    एक वेक्टर का वेक्टर 2D वेक्टर कहलाता है। एल्गोरिदम शुरुआत 2D वेक्टर टाइप का वेरिएबल v घोषित करें वेक्टर v में मान इनिशियलाइज़ करें 2D वेक्टर है: प्रिंट करें for (int i = 0; i < v.size(); i++) for (int j = 0; j < v[i].size(); j++) 2D वेक्टर v[i][j] का मान प्रिंट क