सी ++ में अनुक्रम को मुद्रित करना

मान लीजिए कि हम छोटे अक्षरों की एक लक्ष्य स्ट्रिंग बनाना चाहते हैं।

सबसे पहले, हमारे पास अनुक्रम n '?' है निशान (n लक्ष्य स्ट्रिंग की लंबाई है)। हमारे पास लोअरकेस अक्षरों की मुहर भी है।

प्रत्येक मोड़ पर, हम स्टाम्प को अनुक्रम पर रख सकते हैं, और प्रत्येक अक्षर को उस स्टैम्प से संबंधित अक्षर से बदल सकते हैं। आप 10 * n मोड़ तक बना सकते हैं। एक उदाहरण के रूप में प्रारंभिक अनुक्रम "???????" है, और स्टैम्प "abc" है, तो हम पहले में "abc ??", "?abc?", "??abc" जैसे तार बना सकते हैं। बारी।

यदि अनुक्रम पर मुहर लगाना संभव है, तो सूचकांक की एक सरणी लौटाएं जिसमें प्रत्येक मोड़ पर सबसे बाएं अक्षर पर मुहर लगी हो। यदि यह संभव नहीं है तो एक खाली सरणी लौटाएं। तो जब अनुक्रम "abbc" है, और स्टाम्प "abc" है, तो उत्तर [0, 2] जैसा हो सकता है, क्योंकि हम "?????" -> "एबीसी ??" -> "एबैक"।

इसलिए, यदि इनपुट स्टैम्प ="abcd", target ="abcdbcd" जैसा है, तो आउटपुट [3,0]

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

• एक सरणी रिट परिभाषित करें

• ठीक :=सच

• n :=स्टाम्प का आकार

• टीएसजेड:=0

• जबकि ठीक गैर-शून्य है, करें -

  • ठीक :=असत्य

  • एक्स:=0

  • इनिशियलाइज़ sz के लिए:=स्टैम्प का आकार, जब sz> 0, अपडेट करें (sz को 1 से घटाएँ), करें -

    • इनिशियलाइज़ करने के लिए i:=0, जब i <=स्टैम्प का आकार, अपडेट (i से 1 तक बढ़ाएँ), करें -

      • newStamp :=लंबाई i की '*' की एक स्ट्रिंग + इंडेक्स ito sz-1 से स्टैम्प का सबस्ट्रिंग + '*' की एक स्ट्रिंग जिसका आकार स्टैम्प के आकार के समान है

      • स्थिति :=लक्ष्य में न्यूस्टैम्प की अनुक्रमणिका

      • जबकि पॉज़ लक्ष्य में मौजूद है, करें -

        • ठीक :=सच

        • एक्स:=एक्स + एसजेड

        • रिट के अंत में पोज़ डालें

        • लक्ष्य को स्थिति से स्थिति तक + स्टैम्प के आकार को '*' से भरें।

        • स्थिति :=लक्ष्य में न्यूस्टैम्प की अनुक्रमणिका

  • टीएसजेड:=टीएसजेड + एक्स

• सरणी को उलट दें रिट

• वापसी (यदि tsz लक्ष्य के आकार के समान है, तो रिट करें, अन्यथा एक खाली सरणी)

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

उदाहरण

#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:
   vector<int> movesToStamp(string stamp, string target) {
      vector<int> ret;
      bool ok = true;
      int n = stamp.size();
      int tsz = 0;
      while (ok) {
         ok = false;
         int x = 0;
         for (int sz = stamp.size(); sz > 0; sz--) {
            for (int i = 0; i <= stamp.size() - sz; i++) {
               string newStamp = string(i, '*') +
               stamp.substr(i, sz) + string(stamp.size() - sz - i, '*');
               int pos = target.find(newStamp);
               while (pos != string::npos) {
                  ok = true;
                  x += sz;
                  ret.push_back(pos);
                  fill(target.begin() + pos, target.begin() +
                  pos + stamp.size(), '*');
                  pos = target.find(newStamp);
               }
            }
         }
         tsz += x;
      }
      reverse(ret.begin(), ret.end());
      return tsz == target.size() ? ret : vector<int>();
   }
};
main(){
   Solution ob;
   print_vector(ob.movesToStamp("abcd", "abcdbcd"));
}

इनपुट

"abcd", "abcdbcd"

आउटपुट

[3, 0, ]