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

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

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

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• ok() नामक एक विधि परिभाषित करें, जो स्ट्रिंग s, मैप wordCnt, और n लेती है
• s की एक कॉपी temp में बनाएं
• i को n से s के आकार - 1 तक लूप चलाएं:
  • यदि temp का आकार n का गुणक है, तो:
    • यदि 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 को खाली स्ट्रिंग सेट करें।
• wordCnt का आकार 0 होने पर true वापस करें
• मुख्य विधि से, यह करें:
  • यदि 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 वापस करें

उदाहरण (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; 
    } 
}; 
int main(){ 
    vector<string> v = {"foo", "bar"}; 
    Solution ob; 
    print_vector(ob.findSubstring("barfoothefoobarman", v)); 
}

इनपुट

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

आउटपुट

[0, 9, ]