সি++ এ সিকোয়েন্স স্ট্যাম্পিং

ধরুন আমরা ছোট হাতের অক্ষরগুলির একটি টার্গেট স্ট্রিং তৈরি করতে চাই৷

প্রথমে, আমরা n '?' হিসাবে ক্রম আছে চিহ্ন (n হল টার্গেট স্ট্রিং এর দৈর্ঘ্য)। আমাদের কাছে ছোট হাতের অক্ষরের একটি স্ট্যাম্পও আছে।

প্রতিটি মোড়ে, আমরা সিকোয়েন্সের উপর স্ট্যাম্প স্থাপন করতে পারি, এবং সেই স্ট্যাম্পের সংশ্লিষ্ট অক্ষর দিয়ে প্রতিটি অক্ষর প্রতিস্থাপন করতে পারি। আপনি 10 * n পর্যন্ত পালা করতে পারেন। একটি উদাহরণ হিসাবে বিবেচনা করুন প্রাথমিক ক্রম হল "??????", এবং স্ট্যাম্প হল "abc", তাহলে আমরা প্রথমে "abc??", "? abc?", "?? abc" এর মত স্ট্রিং তৈরি করতে পারি। পালা।

যদি ক্রমটি স্ট্যাম্প করা সম্ভব হয়, তাহলে প্রতিটি মোড়ে স্ট্যাম্প করা বাম-সবচেয়ে অক্ষর সহ সূচকের একটি অ্যারে ফেরত দিন। যদি তা সম্ভব না হয় তাহলে একটি খালি অ্যারে ফেরত দিন। সুতরাং যখন ক্রমটি "ababc" হয়, এবং স্ট্যাম্পটি "abc" হয়, তখন উত্তরটি [0, 2] এর মতো হতে পারে, কারণ আমরা "????" এর মতো গঠন করতে পারি। -> "abc??" -> "ababc"।

সুতরাং, যদি ইনপুট স্ট্যাম্প ="abcd", লক্ষ্য ="abcdbcd" এর মত হয়, তাহলে আউটপুট হবে [3,0]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি অ্যারে ret সংজ্ঞায়িত করুন

• ঠিক আছে :=সত্য

• n :=স্ট্যাম্পের আকার

• tsz :=0

• ঠিক আছে যখন অ-শূন্য, কর −

  • ঠিক আছে :=মিথ্যা

  • x :=0

  • sz আরম্ভ করার জন্য :=স্ট্যাম্পের আকার, যখন sz> 0, আপডেট করুন (sz 1 দ্বারা হ্রাস করুন), করুন −

    • আরম্ভ করার জন্য i :=0, যখন i <=স্ট্যাম্পের আকার, আপডেট (i 1 দ্বারা বৃদ্ধি), −

      • newStamp :=দৈর্ঘ্য i এর '*' একটি স্ট্রিং + ইনডেক্স ito sz-1 থেকে স্ট্যাম্পের সাবস্ট্রিং + '*' এর একটি স্ট্রিং যার আকার স্ট্যাম্পের আকারের সমান

      • pos :=লক্ষ্যে নিউস্ট্যাম্পের সূচক

      • যখন pos লক্ষ্যে উপস্থিত থাকে, −

        করুন

        • ঠিক আছে :=সত্য

        • x :=x + sz

        • ret এর শেষে pos সন্নিবেশ করুন

        • '*' দিয়ে pos থেকে pos + স্ট্যাম্পের সাইজ পর্যন্ত লক্ষ্য পূরণ করুন।

        • pos :=লক্ষ্যে নিউস্ট্যাম্পের সূচক

  • tsz :=tsz + x

• অ্যারে রিভার্স করুন

• রিটার্ন করুন (যদি 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, ]